一、确定有限自动机DFA(Deterninistic FA) 二、确定有限自动机DFA的实现 三、非确定有限自动机NFA(Nondeterninistic FA) 四、 NFA到DFA的转换 五、 DFA的化简

自底向上的语法分析是从给定的符号串出发,试图将它归 约为文法的开始符号. 两种自底向上分析方法: –优先分析法：在文法符号之间确定优先关系，根据优先关 系确定句型的句柄，进行语法分析

常见程序设计语言都不是LR(0)的,所以LR(0)分析表实用性较差.例如,典型的分程序结构:

一、逆波兰------主要用于表达式 1、表达式的逆波兰表示 后缀式: e1e2……ekθ θ是k目运算符(k>=1) 特点:运算量在前,运算符在后,无括号

1965年D.Knuth提出了分析效率很高的LR(k)分 析技术; LR分析: 自左至右扫描的自底向上的分析; 在分析的每一步,只须根据分析栈中的已移进的 和已归约出的符号,并至多向前扫描k个字符就 能确定应采取什么分析动作(移进、归约、接受、 报错); LR分析对文法要求很少,效率很高,且能及时发 现错误,是目前最广泛使用的方法;

对文法进行化简和改造 希望定义语言的文法尽可能简单 某些语法分析技术对文法有要求和限制：LL分析 要求文法无左递归；算符优先分析要求文法不含

3.1 设计扫描器时应考虑的问题 符号的内部表示、识别约定和策略、源程序的输入和预处理 3.2 正规文法和状态转换图 正规文法——状态转换图，状态转换图的实现

2.解： eddfbbd S AbB 1,1.1(表示第 1 步，用产生式 1.1 推导,以下同) CAbbB 2,2.1 edAbbB 3,4.1 edCAbbbB 4,2.1 ededAbbbB 5,4.1(不匹 配) edaAbbbB 5，4.2 (不匹配，回溯到 edAbbB) edBfbbB 4,2.2 edCSdfbbB 5,3.1 ededSdfbbB 6,4.1(不匹配) edaSdfbbB 6,4.2(不匹配，回溯到

One parse tree only a The role of the grammar a distinguish between syntactically legal and illegal programs a But that's not enough: it must also define a parse tree a the parse tree conveys the meaning of the program What if a string can be parsed with multiple parse trees? a we say the grammar is ambiguous a must fix the grammar(the problem is not in the parser) a Note: often a string can be derived in more than one way D ie, with more than one derivation sequence o this does not mean the grammar is ambiguous

yacc代表 Yet Another Compiler Compiler 由S.c. Johnson等人在AT&T贝尔实验室研制开发 的,早期作为UNIX操作系统中的一个实用程序, 现在Yacc得到广泛使用。 yacc有多个版本, Bison是它的一个常用版本