编译原理学习笔记(语法分析)

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

解析器 parseing

再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:(错误纠正):
编译可以帮助提时修改错误。

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

上一篇:爬取渐变风格插画


下一篇:记一次docker compose的低级错误