编译原理课程设计之第五章 自下而上的语法分析推荐.ppt

* YACC(Yet Another Compiler-Compiler)是LALR(1)语法分析器的自动生成工具，它的第一版于70年代初发表，是美国贝尔实验室的软件产品（作者为S.C.Johnson） 5.7 语法分析器自动生成工具—YACC * YACC将一前后文无关文法转换为一LALR(1)分析表,并提供使用该分析表进行语法分析的总控程序yyparse().除此之外，它们还允许用户在产生式中插入语义处理动作进行属性计算。 * 用户按一定规则编写出“文法处理说明文件”，简称YSP(Yacc Specification)文件，文件的扩展名为“.y”； 将YSP输入YACC中，YACC就会自动地构造出相应的C语言形式的语法分析器； 该分析器主要包括由YACC提供的标准总控程序和一个LALR(1)语法分析表。 使用YACC构造语法分析程序 * 一个完整的YSP文件由说明、规则、程序三个部分组成，各部分之间以双百分号“%%”隔开： [说明部分] %% 规则部分 [%% 程序部分] 其中，用方括号括起来的说明部分和程序部分可以空缺，但规则部分则是必需的。 * 语法规则部分是整个YSP文件的主体，它由文法的一组产生式及每一产生式相应的语义动作组成。 对于文法中的每个产生式 在YSP文件中将相应地写成： * A: ?1 {语义动作1；} |?2 {语义动作2；} … |?n {语义动作n；} ； * YACC约定，产生式左部符号的属性值用$$表示，而右部第k个符号用$k表示。 例如，产生式Expr→Expr+Term|Term 在YSP文件中相应地写成： Expr : Expr + Term {$$=$1+$3;} | Term; * 它表示按第一个候选式归约时，左部符号Expr的属性值为该产生式右部第一符号Expr与第三符号Term的属性值之和； 按第二产生式归约时，由于语义动作缺省，YACC自动按{$$=$1}处理(不论右部有多少符号)。 * 本章小结 * 1. 给定文法G[S]: S-SaSb︱c 给出句子 cacbacb 的规范推导，画出该句子的语法推导树，指出该句子的短语和直接短语,句柄。 2. 简述SLR(1)分析方法是如何处理LR(0)分析中出 现的移进——规约冲突和规约——规约冲突的。 作业 * 3. 给定文法G[S]: S-S a A︱A A-b 造文法G[S]的LR(1)项目的DFA。 上述文法构造LR(1)分析表。 写出句子 babab的分析过程。 * THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS THANKS * LR(1)项目：在LR(0)项目中放置一个向右有哪些信誉好的足球投注网站符号a，成为LR(1)项目：[A?α.?,a] LR(1)项目集： LR(1)分析过程中的每个状态，就是包含若干LR(1)项目的一个LR(1)项目集； LR(1)分析 * 项目集规范族: 每个LR(1) 项目集对应一个DFA状态， LR(1)项目集的全体称这个文法的LR(1)项目集规范族。 构造LR(1)项目集族的算法类似于构造LR(0)项目集族的算法，也需要求两个函数CLOSURE和GO。 构造 LR(1)项目集合的DFA： * ① I的任何项目都属于CLOSURE(I)。 若[A??.B?，a]? CLOSURE(I), B?VN , 则任何[B?.?, b]? CLOSURE(I) ，其中 b?First(?a) ③ 重复②直至CLOSURE(I) 不出现新项目为止。 设I是拓广文法G’的一个LR(1)项目集，定义和构造I的闭包函数CLOSURE(I)如下： * I是一个LR(1)项目集， x?VN∪VT，状态转移函数GO(I,x)定义如下： GO(I,x)= CLOSURE(J) 其中J是I识别输入符号x后所到达的项目集，