ps:本文处理的输入为 字符串(如 “3+4*5”…),不为词法分析器分析后的输出的单词流
|| 语法分析的分析规则:上下文无关文法(定义:CFG(N, T, S, R)
- N - Nonterminal - 非终结符
- T - Terminal - 终结符
- S - Start Character - 开始符号
- R - Syntax Rule - 语法规则
|| 语法分析的分析方式:语法分析器有不同的算法可以进行语法分析,一般来说,语法分析的算法分为两种,自顶向下的算法和自底向上的算法,而这两类算法又有很多不同的实现方式,我们只谈最主流的方式
分析栈的语法分析方式
给定文法CFG和待匹配句子s,回答s能否从CFG推导出来?
|| 自顶向下算法:
算法:从G的开始符号出发,随意推出某个句子t,比较s和t:
- 若 t == s ,则回答 “是”
- 若 t != s ,则回答 “否”
tokens[]; // 所有token
i = 0;
stack = [S] // S是开始符号
while (!stack.empty())
if (stack.top() is a terminal t)
if (t == tokens[i])
pop(); //成功
i++;
else
backtrack(); //回溯
else if (stack.top() is a non-terminal T)
pop();
push(next possible choice); // 请注意 possible
当发现匹配错误的时候,分析栈需要回溯到原来的样子,然后再次遍历,效率很低。
|| 递归下降算法(纯手工编码实现语法分析器时常用的算法)
算法:修改push(next possible choice); // 请注意 possible
,不选择 possible ,而是选择 right ,比如我提前看一个符号,我发现是 g ,那么我就直接选择 push g。
代码
parse_S()
parse_N()
parse_V()
parse_N()
parse_N()
token = tokens[i++] // 前看
if (token == s || token = t ...)
return; // OK
error("expect s, t, but given ...")
parse_V()
token = tokens[i++] // 前看
if (token == e || token = d ...)
return; // OK
error("expect e, d, but given ...")
分治法重新实现递归下降算法
parse_X()
token = nextToken()
switch(token)
case 1: parse_E(); eat('+'); parse_T(); // ...
case 2: // ...
...
default: error("expect ..., but given ...");
|| 递归下降算法的二义性问题
若CFG为以下形式,待匹配句子是 3+4*5
E -> E + T
-> T
T -> T * F
-> F
F -> num
代码
parse_E()
token = tokens[i++]
if (token == num)
? // 是调用 E + T 还是调用 T
else
error("expect ..., but given ...")
此时若使用递归下降算法,调用 E + T 和调用 T都是可行的。即产生了二义性
而递归中消除二义性文法就是消除左递归和左因子
代码改进
parse_E()
parse_T()
token = tokens[i++]
while (token == '+')
parse_T()
token = tokens[i++]
parse_T()
parse_F()
token = tokens[i++]
while (token == '*')
parse_F()
token = tokens[i++]
分析表的语法分析方式
ps:(自动生成器里最常用的算法)
|| LL(1)算法
第一个L表示从左到右读程序,第二个L表示每次优先选择最左边的非终结符推导,(1)表示前看1个符号
算法:所谓的表驱动就是给你提供一张表,通过查表你就能决定下一步往哪走。而表驱动算法的主要工作就是把这张表给你算出来。
|| 理想的有表的分析算法
tokens[]; // 所有token
i = 0;
stack = [S] // S是开始符号
while (!stack.empty())
if (stack.top() is a terminal t)
if (t == tokens[i])
pop(); //成功
i++;
else
backtrack(); //回溯
else if (stack.top() is a non-terminal T)
pop();
//!!!!!!push(next possible choice); !!!!!!
/*修改:根据表直接获得正确的值,而不是靠随机选择。避免导致错误而导致的回溯*/
push(next possible choice);
即:有的非终结符作为行,所有的终结符作为列,然后为每一条语法规则标上行号,根据语法规则填表就行
|| 构造一张分析表的方法
|| LR(0)算法(自底向上的分析算法)
同样L表示从左到右读程序,而第二个R表示每次优先选择最右边的非终结符推导,(0)表示前看0个符号
|| 自底向上算法也被称作移进-规约算法(shitf-reduce),主要是因为算法中涉及了两个常用的核心操作,shift和reduce。
|| LR(0)对于原先例子的处理方式:
E -> E + T
-> T
T -> T * F
-> F
F -> num
|| LR算法的实现方式: 同确定性有限自动机DFA,我们要构造的分析表也就是状态转移表
针对以下文法:
0: S -> A$
1: A -> xxB
2: B -> y
代码
stack = []
push($) // EOF
push(1) // 初始化状态
while (true)
token t = nextToken()
state s = stack[top]
if (ACTION[s, t] == "s"+i)
push(t)
push(i)
else if (ACTION[s, t] == "r"+j)
pop(第j条规则的右边全部符号)
state s = stack[top]
push(X) // 把第j条规则的左边非终结符入栈
push(GOTO[s, X]) // 对应的状态入栈
else
error("...")