石河子大学信息科学与技术学院编译原理课件第六章 语法分析――自下而上.ppt

对每个a（包括＃）∈VT，对应两个符号fa，ga。 把所建立的符号尽可能划分为许多组： 若a b，则fa和gb就在一组； 若a b，c b，则fa和fc同组； 建立一个有向图，其结点是上一步中找出的组。 对于任何a和b，若 a b，画 fa→gb 弧，意味着f(a)g(b)； 若 a b，画 gb→fa 弧，意味着f(a)g(b)。 如果上一步结果构成环，则f，g不存在； 否则 f（a）= 从fa组开始的路径和； g (b) = 从gb组开始的路径和。 例 6.8 利用上述分析表，假定输入串为 i * i + i ，描述LR分析器的工作过程。 二义文法的应用 任何二义文法决不是一个LR文法，因而也不是SLR或LALR文法，这是一条定理。 某些二义文法是非常有用的。可采用一定的方式对文法加以限制，保证每个句子只有一颗分析树。 二义性文法的应用 一、使用优先级和结合规则来解决分析动作的冲突 二义文法的应用 文法G7.1有两个明显的好处： 1）如需改变算符的优先级或结合规则无需改变文法自身； 2）文法的分析表所包含的状态肯定比G7.2所包含的状态要少得多。 下面将讨论如何使用LR分析的基本思想，凭借一些其他条件，来分析而已文法所定义的语言。 二义文法的应用 二义文法的应用 在I1,I7,I8中都存在冲突,用任何一种方法解决都会产生冲突。 因此：可用+，*优先级结合LR分析法解决。 规定*优先高于+； *，+是左结合。 故： I7中，*优先高于+，则遇*移入，其它是归约，+左结合 I8中，*优先高于+，则遇*归约，同时*左结合 二义文法的应用 二、悬空else的二义性 二义文法的应用 二义文法的应用 在I4中存在冲突,用任何一种方法解决都会产生冲突。 因此： 规定else必须有if配对。 故： 此处是将e移进。 分析表的自动生成 下面介绍一个编译程序编写系统YACC的基本思想。 YACC能接受用户提供的文法（可能二义）和优先级、结合性质等附加信息，自动产生这个文法的LALR分析表。 思想： 对用户提供的文法，YACC首先产生它的LALR(1)状态，然后试图为每个状态选择适当的分析动作。 如果不存在冲突，无需使用其它附加信息。 如果文法是二义的，则附加信息必不可少。 分析表的自动生成 YACC解决移进-规约冲突的基本方法是赋予每个终结符和产生式一 定的优先级。 假定面临输入符号a时碰到移进和规约(用A?α)的冲突，就比较终结符a和产生式A?α的优先级。若A?α的优先级高，则作规约，否则作移进。 如果对产生式A?α不特别赋予优先级，就认为A?α和出现在α中的最右终结符具有相同的优先级。 分析表的自动生成 我们可以采用如下写法，把一个文法连同它的优先信息提供该YACC： TERMINAL e //优先级高的在前面 TERMINAL i //i的优先级低于e S?iSeS //列出文法的所有产生式 S?iS S?a 分析表的自动生成 也可以通过引进一个优先级低于e的哑终结符的办法，直接指明产生式S?iS的优先级： TERMINAL e TERMINAL dummy //哑终结符dummy的优先级低于e S?iSeS S?iS PRECEDENCE dummy // PRECEDENCE //意味着“优先级等于” S?a 分析表的自动生成 优先级和结合性质的规定解决了冲突。 实际上，左结合意味着实行规约，右结合意味着实行移进。 有些算符不允许结合，这可以用YACC的NONASSOC给以特别指明。 YACC的专用字：LEFT—左结合，TIGHT—右结合，NONASSOC—禁止结合。 TERMINAL +, - LEFT LR分析表的安排 建立一个以状态为下标的一维数组。 它的每一个元素是一个指示器，指向某一ACTION行。 每个ACTION行自身是一个一维数组，以终结符为下标。 对GOTO标中的每个非终结符安排一张包含二元式(当前状态，下一状态)的表。 LR语法分析的错误恢复 在LR分析中，若输入符号既不能移入栈内，栈顶元素也不能归约，就意味着发现错误。LR语法分析器立即给出错误报告。 LR(1)（规范LR）在报告错误前不进行任何无效归约； SLR,LALR则可能会执行几步归约，但不会把出错点的输入符号移入栈内。 LR语法分析的错误恢复 处理办法： 1.使用插入、删