-
-
[原创]论分析 LL(1) 文法的语法分析器中栈的正确使用方法
-
2013-9-25 19:13
3259
-
[原创]论分析 LL(1) 文法的语法分析器中栈的正确使用方法
（
写这篇文章我可能火星了）一个语言的 BNF 描述：
A ::= A + B | A - B | B
B ::= B * C | B / C | C
C ::= Letter | ( A )
其中 Letter 为单个英文字母，消除左递归有：
A ::= B A' A' ::= + B A' | - B A' | eps
B ::= C B' B' ::= * C B' | / C B' | eps
C ::= Letter | ( A )
这样子问题就来了，识别 A 和 A' 如果在两个函数中，其中 A 中识别到最后能出现一个操作数，另外的一个操作数和运算符在 A' 中识别，如果识别 A 和 A' 的函数要求函数原型一样参数为 void，那么又该怎么办呢？然后自己就想到了栈。在产生式 A 中识别的东西先压到栈中，遇到 A' 或者 B' 这样的含有操作符和另一个操作数的产生式时，从栈中弹出原先已经识别好的操作数，然后构建树。下面是一个示范程序，写的非常简洁，输入字符串“(a+b)*(c-d)+e/f*(g)”，结果为：
t2 = a + b
t3 = c - d
t1 = t2 * t3
t5 = e / f
t4 = t5 * g
t0 = t1 + t4
示例程序源代码(C#)：
using System;
using System.Collections.Generic;
using System.IO;
namespace LL1Test
{
static class Character
{
public static bool IsLetter(char chTest)
{
if ((chTest >= 'a' && chTest <= 'z') ||
(chTest >= 'A' && chTest <= 'Z')
) { return true; } else { return false; }
}
}
sealed class TreeNode
{
public TreeNode()
{
this.chData = '\0';
this.LeftNode = null;
this.RightNode = null;
}
private string PrintTree(TextWriter Out, ref int nTag)
{
if (Character.IsLetter(chData))
return chData.ToString();
string strTemp = string.Format("t{0}", nTag++.ToString());
Out.WriteLine("{0} = {2} {1} {3}",
strTemp, this.chData.ToString(),
LeftNode.PrintTree(Out, ref nTag),
RightNode.PrintTree(Out, ref nTag)
); return strTemp;
}
public void PrintTree(TextWriter Out)
{
int nTag = 0;
this.PrintTree(Out, ref nTag);
}
public char chData;
public TreeNode LeftNode;
public TreeNode RightNode;
}
sealed class Parser
{
public Parser(TextWriter OutStream)
{
this.TreeStack = new Stack<TreeNode>();
this.OutStream = OutStream;
this.Initialize(string.Empty);
}
private void Initialize(string strData)
{
this.InputData = strData;
this.DataPosition = 0;
this.LookAhead = '\0';
this.CurrentChar = '\0';
this.HaveError = false;
this.TreeStack.Clear();
this.ReadNextChar();
}
private char ReadNextChar()
{
this.CurrentChar = this.LookAhead;
if (this.DataPosition > this.InputData.Length + 1)
return this.CurrentChar;
int nPos = this.DataPosition + 1;
if (this.DataPosition >= this.InputData.Length)
this.LookAhead = '\0';
else
this.LookAhead = this.InputData[this.DataPosition];
this.DataPosition = nPos;
return this.CurrentChar;
}
private void Parse_A()
{
this.Parse_B(); this.Parse_Ax();
}
private void Parse_Ax()
{
if (this.LookAhead == ')' || this.LookAhead == '\0')
return;
if (this.LookAhead == '+' || this.LookAhead == '-')
{
TreeNode OperateNode = new TreeNode();
OperateNode.chData = this.ReadNextChar();
OperateNode.LeftNode = this.TreeNode_Pop();
this.Parse_B();
OperateNode.RightNode = this.TreeNode_Pop();
this.TreeNode_Push(OperateNode);
this.Parse_Ax(); return;
}
this.SyntaxError();
}
private void Parse_B()
{
this.Parse_C(); this.Parse_Bx();
}
private void Parse_Bx()
{
if (this.LookAhead == '+' || this.LookAhead == '-' ||
this.LookAhead == ')' || this.LookAhead == '\0'
) { return; }
if (this.LookAhead == '*' || this.LookAhead == '/')
{
TreeNode OperateNode = new TreeNode();
OperateNode.chData = this.ReadNextChar();
OperateNode.LeftNode = this.TreeNode_Pop();
this.Parse_C();
OperateNode.RightNode = this.TreeNode_Pop();
this.TreeNode_Push(OperateNode);
this.Parse_Bx(); return;
}
SyntaxError();
}
private void Parse_C()
{
if (Character.IsLetter(this.LookAhead))
{
TreeNode LetterNode = new TreeNode();
LetterNode.chData = this.ReadNextChar();
this.TreeNode_Push(LetterNode); return;
}
if (this.LookAhead == '(')
{
this.ReadNextChar(); this.Parse_A();
if (this.LookAhead == ')') {
this.ReadNextChar(); return; }
}
this.SyntaxError();
}
private void SyntaxError()
{
if (this.HaveError != false) { return; }
if (this.DataPosition > this.InputData.Length)
{
this.OutStream.WriteLine("非法的输入数据结束。");
}
else
{
this.OutStream.Write("语法解析失败在第 ");
this.OutStream.Write(this.DataPosition);
this.OutStream.WriteLine(" 个字符处。");
}
this.HaveError = true;
}
private void TreeNode_Push(TreeNode Node)
{
if (this.HaveError) { return; }
else { this.TreeStack.Push(Node); }
}
private TreeNode TreeNode_Pop()
{
if (this.HaveError) { return null; }
else { return this.TreeStack.Pop(); }
}
public TreeNode ParseString(string strData)
{
this.Initialize(strData);
this.Parse_A();
return this.TreeNode_Pop();
}
private int DataPosition;
private char LookAhead;
private char CurrentChar;
private Stack<TreeNode> TreeStack;
public bool HaveError { get; private set; }
public string InputData { get; private set; }
public TextWriter OutStream { get; private set; }
}
class Program
{
public static int Main(string[] args)
{
Console.Write("请输入您要转换的表达式：");
string strUserInput = Console.ReadLine();
Parser TestParser = new Parser(Console.Out);
TreeNode Result = TestParser.ParseString(strUserInput);
if (Result != null) { Result.PrintTree(Console.Out); }
// Console.WriteLine("程序运行完成！！~");
// Console.ReadKey();
return 0;
}
}
}
[CTF入门培训]顶尖高校博士及硕士团队亲授《30小时教你玩转CTF》，视频+靶场+题目！助力进入CTF世界
