编译原理学习笔记（语法分析）

2024-01-10 15:51:34

内容来自斯坦福的公开课等内容

再Cool语言中，有条件分支的表达式如下：

if x = y
	then 1
else 2
fi

经过词法分析器后得到token如下：
IF ID = ID THEN INT ELSE INT FI

token经过parser后，得到一个解析树。（正常的解析会将lexer与parser的部分一起操作，而且可能不会构建一个完整的解析树）
上下文无关文法:

上下文无关文法由如下组成：
终结符 T，非终结符N，起始符S，产生式集合

例子:

非终结符N= {S}
T={(,)}

S->(S)
S->ε

COOL语言样例：

EXPR - > if EXPR then EXPR else EXPR fi

上面的EXPR就是非终结符，if then else fi这四个都是是终结符

另一个例子，并将上面的条件语句组合：
（EXPR是非终结符）

EXPR - > if EXPR then EXPR else EXPR fi
EXPR - > while EXPR loop EXPR pool
EXPR -> id

可以合并写成：

EXPR - > if EXPR then EXPR else EXPR fi
			| while EXPR loop EXPR pool
			| id

很明显，EXPR是开始符，有EXPR->id

例子3：
算术表达式

E->E + E
	| E * E
	| (E)
	| id

目前上下文无关文法只能给出当前输入的字符串是否是符合规范，还需要对它进行解析(parser)，而且还能处理错误

推导：

根据产生式构建parse tree

parse tree包括：叶子节点是终结符，非终结符是内部节点（interior nodes）

中序遍历parse的叶子节点，得到输入信息，最后parse tree得到运算之间的关系。
但是parse tree没有表现出运算符的优先级，比如乘法和加法之间的优先性

最左/最右推导：
每次将最左侧/右侧的非终结符展开，得到对应的parse tree.

歧义性：
有如下语法：

E->E + E | E * E | (E) | id

给定字符串 id * id + id

上面的字符串使用最左推导或最右推导，得到两个不同的parse tree

如果一个语法能得到超过一个parse tree，那么就称这个语法是歧异的。换个说法，某个字符串右多个最左最右推导。

重写语法，消除歧异。

E->E' + E | E'
E'->id * E' | id | (E) * E' | (E)

上面E负责加法部分，E’负责乘法部分

这里将语法做了分层，消除了歧异：

E->E'+E => E' + E' + E => E' + E' + E' +E ....

包括词法错误、语法错误、语义错误等，在编译的时候应该给出提示。

panic mode（紧急模式）：
当错误被检测到时，解析器会抛弃token，直到在语言中找到一个正确的token为止。
寻找这些token的过程称为（synchronizing token)
比如有表达式：

(1++2)+3

解析器在遇到第二个加号后会在数字2重新开始解析

bison：
一种常用的解析生成器，比如有如下的语法规则：

E->int | E + E | (E) | error int | (error)

error productions（错误产生式）：

在语法规则中指出常见的错误类型，比如：
两个表达式相乘5×a，可能写成5a，而不是5*a
可以在产生式中添加： E − > . . . ∣ E E E->...|EE E−>...∣EE来实现错误提示。
缺点是会增加语法的复杂性。

error correction：（错误纠正）：
编译可以帮助提时修改错误。

缺点，很复杂，速度很慢。

码农公寓