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

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

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

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

句型的分析：构造一算法，用以判断所给的符号串是否为某文法的句型 常见分析方法有自顶向下分析和自底向上分析两类；

程序设计语言 低级语言：机器语言（二进制代码）、汇编语言（直 接操作寄存器、多种寻址方式）及其它面向机器的程 序设计语言；其特点对计算机的依赖性强、直观性差、 编写程序的工作量大，对程序设计人员要求较高

2.5.1.1归约(Reduce) 自下而上(Bottom--Up)分析采用“移进一归约 ”(shift-reduce-)的基本思想 ·把输入符号逐个移进到一个符号栈,当栈顶形成 某个产生式的候选式时,即把栈顶的这一部分替换 成(归约为)该产生式的左部符号

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是它的一个常用版本

• Lex 代表 Lexical Analyzar • 使用LEX工具可根据描述语言的词法构成规则的正规式来自动生成扫描程序。 • LEX在unix平台上使用，在windows平台上的一种常用实现是FLEX，它是GNU compiler package的一部分