Chapter04_Syntax Analysis语法分析.ppt

北京化工大学信息科学与技术学院计算机系赵瑞莲rlzhao 编译原理 2020 2 18 北京化工大学信息科学与技术学院计算机系 2 Chapter4SyntaxAnalysis语法分析 4 1语法分析器的作用4 2上下文无关文法4 3自顶向下语法分析4 4自底向上语法分析 2020 2 18 北京化工大学信息科学与技术学院计算机系 3 4 1语法分析器的作用 词法分析 源程序 目标程序 语法分析 语义分析 中间代码优化 中间代码生成 Thephaseofacompiler编译程序的结构 目标代码生成 2020 2 18 北京化工大学信息科学与技术学院计算机系 4 4 1语法分析器的作用 语法分析器 词法分析器 记号流 源程序 前端其他部分 分析树 中间表示 符号表管理器 出错处理器 2020 2 18 北京化工大学信息科学与技术学院计算机系 5 源程序中可能出现的错误 词法错误如非法字符或拼写错关键字 标识符等 如 intege20times 语法错误是指语法结构出错 如少分号 begin end不配对等 beginx a by x 4 1语法分析器的作用 2020 2 18 北京化工大学信息科学与技术学院计算机系 6 源程序中可能出现的错误 词法错误 语法错误 静态语义错误 动态语义错误 逻辑错误 4 1语法分析器的作用 如非法字符或拼写错关键字 标识符等 intege20times 是指语法结构出错 如少分号 begin end不配对等 beginx a b y x 如无穷递归 变量为零时作除数等 while t a a b 类型不一致 参数不匹配等 如a b integer x array 1 10 ofinteger x a b 2020 2 18 北京化工大学信息科学与技术学院计算机系 7 语法错误处理的目标清楚而准确地报告错误的出现 地点正确 不漏报 不错报也不多报 迅速地从每个错误中恢复过来 以便分析继续进行 不应使对语法正确源程序的分析速度降低太多 4 1语法分析器的作用 2020 2 18 北京化工大学信息科学与技术学院计算机系 8 4 2Context freegrammars上下文无关文法 2020 2 18 北京化工大学信息科学与技术学院计算机系 9 4 2 1上下文无关文法概述 4 2 1 1Comparisontoregularexpressionnotation与正则表达式比较 thecontext freegrammar number numberdigit digit digit 0 1 2 3 9 theregularexpression number digitdigit digit 0 l 2 3 4 5l6 7 8 9 thecontext freegrammar exp expopexp exp numberop 2020 2 18 北京化工大学信息科学与技术学院计算机系 10 4 2 2 1Specificationofcontext freegrammarrules上下文无关文法规则的说明 什么是文法 文法是对语言结构的定义与描述 即从形式上用于描述和规定语言结构的称为 文法 或称 语法 例 请判断英语句子Thebigelephantatethepeanut 语法上是否正确 2020 2 18 北京化工大学信息科学与技术学院计算机系 11 the big elephant peanut ate 解 1 已知语法规则 2020 2 18 北京化工大学信息科学与技术学院计算机系 12 the thebig thebigelephant thebigelephant thebigelephantate thebigelephantate thebigelephantatethe thebigelephantatethepeanut the big elephant peanut ate 2020 2 18 北京化工大学信息科学与技术学院计算机系 13 Note 2020 2 18 北京化工大学信息科学与技术学院计算机系 14 4 2 2 2Derivationsandthelanguagedefinedbyagrammar推导及由文法定义的语言 1 相应的正则式 2 derivation推导 例 根据文法 请判断程序 34 3 42语法上是否正确 exp expopexp exp numberop 1 exp expopexp exp expopexp 2 expopnumber exp number 3 exp number op 4 exp number exp exp 5 expopexp number exp expopexp 6 expopnumber number exp number 7 exp number number op 8 number number number exp number number number number 2020 2 18 北京化工大学信息科学与技术学院计算机系 15 L G s exp s 文法定义的 产生的 语言 exp 开始符号thestartsymbol 星推导 正推导 s 句子 exp expopexp exp numberop exp 开始符号thestartsymbolexp number 产生式Nonterminals 非终结符 Terminals 终结符 文法 2020 2 18 北京化工大学信息科学与技术学院计算机系 16 Example 1 已知文法G E E a 请问文法定义的语言是什么 L G a a a a na n naninteger 0 2 已知文法G E E 请问文法定义的语言是什么 空 3 已知文法G E E a a 请问文法定义的语言是什么 L G a a a a a a a a a a 4 已知正则式为a 请问相应的文法及定义的语言是什么 G A Aa aorA aA a L a an naninteger 0 5 已知正则式为a 请问相应的文法是什么 G A Aa orA aA Recursive递归Grammar文法A A A A 2020 2 18 北京化工大学信息科学与技术学院计算机系 17 Example 6 已知文法定义的语言如下 C的嵌套if语句 请写出该文法 otherif 0 otherif 1 otherif 0 otherelseotherif 1 otherelseother if 0 if 0 otherif 0 if 1 otherelseotherif 1 otherelseif 0 otherelseother 2020 2 18 北京化工大学信息科学与技术学院计算机系 18 Example 7 已知文法A A A 请问 语法正确吗 A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A A 语法正确 2020 2 18 北京化工大学信息科学与技术学院计算机系 19 Example 8 已知文法G如下 请问文法定义的语言是什么 stmt sequence stmt stmt sequence stmtstmt s L G s s s s s s 若例8中允许语句序列为空 即定义的语言为L G s s s s s s 则相应的文法是什么 stmt sequence stmt stmt sequence stmt s 若例8中允许语句序列为空 但要求分号作为语句分隔符 即定义的语言为L G s s s s s s 则相应的文法是什么 stmt sequence nonempty stmt sequence nonempty stmt sequence stmt nonempty stmt sequence stmtstmt s 2020 2 18 北京化工大学信息科学与技术学院计算机系 20 Example 若例8中允许语句序列为空 但要求分号作为语句结束符 即定义的语言为L G s s s s s s s s s 则相应的文法是什么 stmt sequence stmt other1stmt other2stmt other1 stmt stmt other2 stmtstmt other2 stmt s 2020 2 18 北京化工大学信息科学与技术学院计算机系 21 4 2 3Parsetreesandabstractsyntaxtrees分析树与抽象的语法树 1 exp expopexp exp expopexp 2 exp opexp exp exp 3 expopexp opexp exp expopexp 4 numberopexp opexp exp number 5 number exp opexp op 6 number number opexp exp number 7 number number exp op 8 number number number exp number derivation推导 最右推导 最左推导 2020 2 18 北京化工大学信息科学与技术学院计算机系 22 1 推导 1 exp expopexp 2 numberopexp 3 number exp 4 number number 1 exp expopexp 2 expopnumber 3 exp number 4 number number 分析树 与推导相对应的作了标记的树 2 分析树 1 exp expopexp 2 exp exp 3 number exp 4 number number exp number number exp number number exp number number 2020 2 18 北京化工大学信息科学与技术学院计算机系 23 1 exp expopexp 2 exp opexp 3 expopexp opexp 4 numberopexp opexp 5 number exp opexp 6 number number opexp 7 number number exp 8 number number number derivation推导 2020 2 18 北京化工大学信息科学与技术学院计算机系 24 1 表达式3 4的分析树 Abstractsyntaxtrees抽象语法树 简称语法树 2 语法树 exp OpExp op exp exp ConstExp integer op Plus Minus Times 3 简单的算术表达式抽象语法树的文法 例1 简单表达式的抽象语法树 解 2020 2 18 北京化工大学信息科学与技术学院计算机系 25 typedefenum Plus Minus Times OpKindtypedefenum OpK ConstK ExpKind typedefstructstreenode ExpKindkind OpKindop structstreenode lchild rchild intval STreeNode typedefSTreeNode SyntaxTree 4 简单的算术表达式抽象语法树的存储结构 2020 2 18 北京化工大学信息科学与技术学院计算机系 26 解 分析树 例2 if语句的抽象语法树 1 已知简化了的if语句的文法 statement if stmt otherif stmt if exp statement if exp statementelsestatementexp 0 1请画出串if 0 otherelseother的语法树 2020 2 18 北京化工大学信息科学与技术学院计算机系 27 解 分析树 2 已知文法 statement if stmt otherif stmt if exp statementelse partelse part elsestatement exp 0 1请画出串if 0 otherelseother的语法树 2020 2 18 北京化工大学信息科学与技术学院计算机系 28 3 if语句的抽象语法树 4 if语句的存储表示 typedefenum ExpK StmtK NodeKind typedefenum Zero One ExpKind typedefenum IfK OtherK StmtKind typedefstructstreenode NodeKindkind ExpKindekind StmtKindskind structstreenode test thenpart elsepart STreeNode typedefSTreeNode SyntaxTree 2020 2 18 北京化工大学信息科学与技术学院计算机系 29 解 分析 例3 顺序结构的语句的抽象语法树 1 已知顺序结构的语句的文法 stmt sequence stmt stmt sequence stmtstmt s请画出串s s s的语法树 stmt sequence stmt stmt sequence s stmt s s stmt sequence stmt 2020 2 18 北京化工大学信息科学与技术学院计算机系 30 2 顺序结构的语句的抽象语法树 2020 2 18 北京化工大学信息科学与技术学院计算机系 31 4 2 4Ambiguity二义性 4 2 4 1AmbiguousGrammars二义性文法 例 已知简单整型算术文法 exp expopexp exp numberop 请画出串34 3 42的语法树 解 1 推导2 分析树3 语法树 2020 2 18 北京化工大学信息科学与技术学院计算机系 32 解 1 最左推导 例 已知简单整型算术文法exp expopexp exp numberop 请画出串34 3 42的分析树 exp expopexp expopexpopexp numberopexpopexp number expopexp number numberopexp number number exp number number numberandexp expopexp numberopexp number exp number expopexp number numberopexp number number exp number number number 2 分析树 2020 2 18 北京化工大学信息科学与技术学院计算机系 33 例 已知简单整型算术文法exp expopexp exp numberop 请画出串34 3 42的分析树 3 语法树 ambiguousgrammar二义性文法 可生成两个不同分析树的串的文法叫二义性文法 消除二义性规则 不修改文法 指定正确的分析树 或语法树 修改文法 优先级 结合性 2020 2 18 北京化工大学信息科学与技术学院计算机系 34 4 2 4 2Precedenceandassociativity优先级和结合性 precedencecascade优先级联 具有相同优先级的算符归纳在一组 并为每一种优先级规定不同的规则 例 将 乘法比加法和减法优先 添加到简单的算术表达式文法 exp expaddopexp termaddop term termmulopterm factormulop factor exp number 2020 2 18 北京化工大学信息科学与技术学院计算机系 35 结合性 例 将 乘法比加法和减法优先 并且左结合 添加到简单的算术表达式文法 exp expaddopterm termaddop term termmulopfactor factormulop factor exp number exp expaddopexp term 2020 2 18 北京化工大学信息科学与技术学院计算机系 36 4 2 4 3Thedanglingelseproblem悬挂else问题 例 文法是二义性文法吗 statement if stmt otherif stmt if exp statement if exp statementelsestatementexp 0 1 解 串if 0 if 1 otherelseother的分析树1 2020 2 18 北京化工大学信息科学与技术学院计算机系 37 statement if stmt otherif stmt if exp statement if exp statementelsestatementexp 0 1 串if 0 if 1 otherelseother的分析树2 2020 2 18 北京化工大学信息科学与技术学院计算机系 38 statement if stmt otherif stmt if exp statement if exp statementelsestatementexp 0 1 mostcloselynestedrule用于悬挂else问题的最近嵌套规则 消除二义性的规则 statement matched stmt unmatched stmtmatched stmt if exp matched stmtelsematched stmt otherunmatched stmt if exp statement if exp matched stmtelseunmatched stmtexp 0 1 最近嵌套规则 matched stmt 匹配的语句 不含不带else的if语句的语句 unmatched stmt 不匹配的语句 含不带else的if语句的语句 2020 2 18 北京化工大学信息科学与技术学院计算机系 39 statement if stmt otherif stmt if exp statement if exp statementelsestatementexp 0 1 消除二义性的规则方法2 if stmt ifconditionthenstatement sequenceendif ifconditionthenstatement sequenceelsestatement sequenceendif 2020 2 18 北京化工大学信息科学与技术学院计算机系 40 4 2 4 4Inessentialambuguity无关紧要二义性 文法有二义性 但总生成唯一的抽象的语法树 例 如下文法是无关紧要二义性文法 stmt sequence stint sequence stmt sequence stmtstmt s 2020 2 18 北京化工大学信息科学与技术学院计算机系 41 4 2 5extendednotations EBNFandsyntaxdiagrams扩展的表示法 EBNF和语法图 extendedBNF orEBNF表示法 1 递归 重复 表示 左递归 A A A A 右递归 A A A A 文法 正则式 EBNF 2020 2 18 北京化工大学信息科学与技术学院计算机系 42 2 选择 表示 statement if stmt otherif stmt if exp statement elsestatement exp 0 1 例 stmt Sequence stmt stmt Sequence stmtstmt s 解 stmt sequence stmt stmt rightrecursiveform stmt sequence stmt stmt leftrecursiveform 例 stmt sequence stmt stmt sequence stmt 解 stmt sequence stmt stmt sequence 2020 2 18 北京化工大学信息科学与技术学院计算机系 43 4 2 6Formalpropertiesofcontext freelanguage上下文无关语言的形式特性 4 2 6 1Aformaldefinitionofcontext freelanguage上下文无关文法的形式定义G T N P S AsetTofterminals 终结符集合T AsetNofnonterminals disjointfromT 非终极符集合N 与T不相交 AsetPofproductions orgrammarrules oftheformA a whereAisanelementofNandaisanelementof T N 产生式或文法规则A a集合P 其中A N a T N AstartsymbolSfromthesetN 开始 识别 符号 N thesetofsymmbols 符号集 T NT N A a 其中 A 1 a 0 注 2020 2 18 北京化工大学信息科学与技术学院计算机系 44 P 0 1 9 S 例 无符号整数的文法如下 可否化简 G N T P S N T 0 1 2 3 9 2020 2 18 北京化工大学信息科学与技术学院计算机系 45 文法的简化方法 产生式左边符号构成集合N 且S N 具有相同的左部的产生式 可以合在一起 解 无符号整数的文法简化为 产生式集合 开始符号 G 0 1 2 3 9 2020 2 18 北京化工大学信息科学与技术学院计算机系 46 文法G T N P S 的相关术语 G T N P S 其中v aA w a A Na T N 若A P 则aA a 即v w称为v直接产生w 或w是v直接推导 或w直接规约到v 1 直接推导 2020 2 18 北京化工大学信息科学与技术学院计算机系 47 2 推导 G T N P S a a1 an 其中a T N 若a1 a2a2 a3 an 1 an即a 称为a推导出 产生 推导长度为n 或 规约到a 例 1 10即 10 G T N P S a T N 若a 或a 称为a推导出 产生 推导长度为n 或 规约到a 2020 2 18 北京化工大学信息科学与技术学院计算机系 48 4 leftmostderivation最左推导 G T N P S S w 每个推导步骤aA a 都有A N T N a T 称为S w为最左推导 最左推导 若符号串中有两个以上的非终结符时 先推左边的 最右推导 若符号串中有两个以上的非终结符时 先推右边的 5 rightmostderivation最右推导 规范推导 G T N P S S w 每个推导步骤aA a 都有A N a T N T 称为S w为最右推导 2020 2 18 北京化工大学信息科学与技术学院计算机系 49 6 sententialform 句型 G T N P S S a a T N 称a为句型 7 sentence 句子 G T N P S S a a T 称a为句子 8 文法产生的语言L G S G T N P S L G S a S a a T 称L G S 为文法G产生的语言 2020 2 18 北京化工大学信息科学与技术学院计算机系 50 9 短语 简单短语 G T N P S w xuy T N 为文法的句型 若S xUy 且U u 则u是句型w相对于U的短语 若S xUy 且U u 则u是句型w相对于U的简单短语 其中U N u T N x y T N 10 句柄 任一句型的最左简单短语称为该句型的句柄 短语 简单短语是相对于句型而言 一个句型可能有多个短语 简单短语 句柄只能有一个 Note 2020 2 18 北京化工大学信息科学与技术学院计算机系 51 Example E T F i F 解 E E T i F E T i F是G的一句型 2020 2 18 北京化工大学信息科学与技术学院计算机系 52 2020 2 18 北京化工大学信息科学与技术学院计算机系 53 11 文法G的分析树 1 Eachnodeislabeledwithaterminaloranonterminalor 2 TherootnodeislabeledwiththestartsymbolS 3 Eachleafnodeislabeledwithaterminalorwith 4 Eachnonleafnodeislabeledwithanonterminal 5 IfanodewithlabelA NhasnchildrenwithlabelsX1 X2 Xn whichmaybeterminalsornonterminals thenA X1X2 Xn P aproductionofthegrammar 每个分析树只有唯一的一个最左推导和一个最右推导 最左推导与分析树的前序编号相对应 最右推导与分析树的后序编号相对应 Note 2020 2 18 北京化工大学信息科学与技术学院计算机系 54 4 2 6 2Thechomskyhierarchy乔姆斯基层次 文法和语言分类 0型 1型 2型 3型 乔姆斯基层次 2020 2 18 北京化工大学信息科学与技术学院计算机系 55 2020 2 18 北京化工大学信息科学与技术学院计算机系 56 0型 1型 2型 3型比较 3型 P U t或U Wt其中U W Nt T 2型 P U v其中U N v T N 0型 P u v其中u T N v T N 1型 P xUy xuy其中U N x y u T N L3 L2 L1 L0 附 自动机 正则文法 正则表达式的相互转化 正则文法 NFA 正则表达式 1 2 3 4 5 6 DFA 最小化 1 有穷自动机 正则文法 1 对转换函数T A t B 可写成一个产生式 A tB 算法 2 对可接受状态Z 增加一个产生式 Z 3 有穷自动机的初态对应于文法的开始符号 有穷自动机的字母表为文法的终结符号集 例 求出如图NFA等价的正则文法G 1 对转换函数T A t B 可写成一个产生式 A tB 2 对可接受状态Z 增加一个产生式 Z 3 有穷自动机的初态对应于文法的开始符号 有穷自动机的字母表为文法的终结符号集 2 正则文法G 有穷自动机M 算法 1 字母表与G的终结符号相同 2 为G中的每个非终结符生成M的一个状态 G的开始符号S是开始状态S 3 增加一个新状态Z 作为NFA的终态 4 对G中的形如A tB的产生式 其中t为终结符或 A和B为非终结符 构造M的一个转换函数f A t B 5 对G中的形如A t的产生式 构造M的一个转换函数f A t Z 例 求与文法G E 等价的NFAG E E aA bB A aB bAB aE bA 解 1 字母表与G的终结符号相同 2 为G中的每个非终结符生成M的一个状态 G的开始符号S是开始状态S 3 增加一个新状态Z 作为NFA的终态 4 对G中的形如A tB的产生式 其中t为终结符或 A和B为非终结符 构造M的一个转换函数f A t B 5 对G中的形如A t的产生式 构造M的一个转换函数f A t Z 3 正则式 有穷自动机 1 a 对于正则式 所构造NFA x y b 对于正则式 所构造NFA x y c 对于正则式a a 则NFA x y a 2 若s t为 上的正则式 相应的NFA分别为N s 和N t a 对于正则式R s t NFA R b 对正则式R st NFA R c 对于正则式R s NFA R d 对R s 与R S的NFA一样 例 为R a b abb构造NFA 使得L N L R 分解R的方法有很多种 R a b abb 4 有穷自动机 正则式 例 M如下 求相应的正则表达式 解 加x y 新的初态和终态 消除M中的所有结点 解 加x y 新的初态和终态 利用以下转换规则 直至只剩下一个开始符号定义的产生式 并且产生式的右部不含非终结符 规则 规则1 规则2 规则3 文法产生式 正则式 A xB B y A xA y A x A y A xy A x y A x y 5 正则文法 正则式 例 有文法G s S aA aA aA dA a d求相应的正则表达式 解 A aA dA a d a d A a d a d a d 代入规则1得 S a a d a d a S a a d a d 算法 1 对任何正则式r 选择一个非终结符S作为识别符号 并产生产生式S r2 若x y是正则式 例 将R a a d 转换成相应的正则文法 解 1 S a a d 2 S aAA a d S aAA a d AA S aAA aA dAA 6 正则式 正则文法 规则 规则1 规则2 规则3 2020 2 18 北京化工大学信息科学与技术学院计算机系 70 4 2 7SyntaxoftheTINYlanguageTINY语言的语法 2020 2 18 北京化工大学信息科学与技术学院计算机系 71 program stmt sequencestmt sequence stmt sequence statement statementstatement if stmt repeat stmt assign stmt read stmt write stmtif stmt ifexpthenstmt sequenceend ifexpthenstmt sequenceelsestmt sequenceendrepeat stmt repeatstmt sequenceuntilexpassign stmt identifier expread stmt readidentifierwrite stmt writeexpexp simple expcomparison opsimple exp simple expcomparison op simple exp simple expaddopterm termaddop term termmulopfactorfactor factormulop factor exp number identifier 4 2 7 1Acontext freegrammarforTINY 2020 2 18 北京化工大学信息科学与技术学院计算机系 72 TINY基本结构类型 4 2 7 2SyntaxtreestructurefortheTINYcompiler if statementsif语句repeat statementsrepeat语句assign statementsassign语句read statementsread语句write statementswrite语句 operator expressions算符表达式constant expressions常量表达式identifier expression标识符表达式 statements语句Expressions表达式 2020 2 18 北京化工大学信息科学与技术学院计算机系 73 语法树结构的图形描述 矩形 表示语句节点 圆形和椭圆 表示表达式节点 三角形 表示额外的非指定的树结构 2020 2 18 北京化工大学信息科学与技术学院计算机系 74 语法树结构的图形描述 2020 2 18 北京化工大学信息科学与技术学院计算机系 75 typedefenum StmtK ExpK NodeKind typedefenum IfK RepeatK AssignK ReadK WriteK StmtKind typedefenum OpK ConstK IdK BxpKind ExpTypeisusedfortypechecking typedefenum Void Integer Boolean ExpType CdeclarationsforaTINYsyntaxtreenode 2020 2 18 北京化工大学信息科学与技术学院计算机系 76 defineMAXCHILDREN3typedefstructtreeNode structtreeNode child MAXCHILDREN structtreeNode sibling intlineno NodeKindnodekind union StmtKindstmt ExpKindexp kind union TokenTypeop intval char name attr ExpTypetype fortypecheckingofexps TreeNode 2020 2 18 北京化工大学信息科学与技术学院计算机系 77 4 3Top DownParsing自顶向下的分析 4 3 1TOP DOWNPARSINGBYRECURSIVE DESCENT使用递归下降分析算法进行自顶向下的分析4 3 2LL 1 PARSINGLL 1 分析4 3 3FIRSTANDFOLLOWSETSFIRST集合和FOLLOW集合 2020 2 18 北京化工大学信息科学与技术学院计算机系 78 Parsing语法分析方法 Recursive descentparsing递归下降法LL 1 parsingLL 1 分析法 Backtrackingparsers回溯分析方法Predictiveparsers预测分析方法 LR 0 parsingSLR 1 parsingLR 1 parsingLALR 1 parsing 2020 2 18 北京化工大学信息科学与技术学院计算机系 79 4 3 1Top downParsingbyRecursive descent使用递归下降分析算法进行自顶向下的分析 TheideaofRecursive DescentParsing 递归下降法 将一个非终结符A的文法规则看作将识别A的一个过程的定义 A的文法规则的右部指出此过程的代码结构 2020 2 18 北京化工大学信息科学与技术学院计算机系 80 expr expraddopterm termaddop term termmulopfactor factormulop factor expr number example 已知表达式文法 及factor的文法规则 使用递归下降法识别factor 2020 2 18 北京化工大学信息科学与技术学院计算机系 81 4 3 2LL 1 PARSINGLL 1 分析 Mainidea LL 1 Parsingusesanexplicitstackratherthanrecursivecallstoperformaparse LL 1 分析使用显式栈而不是递归调用来完成分析 example 已知G S S S 请应用LL 1 分析方法解 L G 2020 2 18 北京化工大学信息科学与技术学院计算机系 82 已知G S S S 请应用LL 1 分析方法解 L G example 6 接受 1 SS S S S 5 SS S 3 S SS S S 4 S S 匹配 2 S S S S 匹配 S S S S S S S S S 2020 2 18 北京化工大学信息科学与技术学院计算机系 83 4 3 2 2TheLL 1 ParsingTableandAlgorithm PurposeoftheLL 1 ParsingTable Toexpressthepossiblerulechoicesforanon terminalAwhentheAisatthetopofparsingstackbasedonthecurrentinputtoken thelook ahead example TheLL 1 ParsingtableM N T forthefollowingsimplegrammar S S S 2020 2 18 北京化工大学信息科学与技术学院计算机系 84 IfA isaproductionchoice andthereisaderivation a whereaisatoken thenaddA tothetableentryM A a IfA isaproductionchoice andtherearederivations andS Aa whereSisthestartsymbolandaisatoken or thenaddA tothetableentryM A a Thetable constructingrule Supposedthatthetableisoriginallyempty AgrammarisanLL 1 grammariftheassociatedLL 1 parsingtablehasatmostanproductionineachtableentry AnLL 1 grammarcannotbeambiguous DefinitionofLL 1 Grammar 2020 2 18 北京化工大学信息科学与技术学院计算机系 85 assumes marksthebottomofthestackandtheendoftheinput pushthestartsymbolontothetoptheparsingstack whilethetopoftheparsingstack andthenextinputtoken doifthetopoftheparsingstackisterminalaandthenextinputtoken athen match poptheparsingstack advancetheinput elseifthetopoftheparsingstackisnon terminalAandthenextinputtokenisterminalaandparsingtableentryM A a containsproductionA X1X2 Xnthen generate poptheparsingstack fori ndownto1dopushXiontotheparsingstack elseerror AParsingAlgorithmUsingtheLL 1 ParsingTable ifthetopoftheparsingstack andthenextinputtoken thenacceptelseerror 2020 2 18 北京化工大学信息科学与技术学院计算机系 86 example statement if stmt otherif stmt if exp statementelse partelse part elsestatement exp 0 1 statement if stmt statement other if stmt if exp Statementelse part else part elsestatementelse part Exp 0 Exp 1 else part TheLL 1 parsingtableforsimplifiedgrammarofif statements M else part else thedanglingelseambiguity Disambiguatingrule else part elsestatementelse part if stmt if exp Statementelse part 2020 2 18 北京化工大学信息科学与技术学院计算机系 87 2 分析if 0 if 1 otherelseother过程 缩写i 0 i 1 oeo 60 SL 0 i 1 oeo 匹配 1S i 0 i 1 oeo S I 5E SL 0 i 1 oeo E 0 3i E SL i 0 i 1 oeo 匹配 4 E SL 0 i 1 oeo 匹配 2I i 0 i 1 oeo I i E SL ifotherelse 01 statementif stmtelse partexp statement if stmt statement other if stmt if exp statementelse part else part elsestatement Exp 0 Exp 1 else part 解 1 分析表 if stmt if exp statementelse part 2020 2 18 北京化工大学信息科学与技术学院计算机系 88 2 分析if 0 if 1 otherelseother过程 缩写i 0 i 1 oeo 12E SLL 1 oeo E 1 7 SL i 1 oeo 匹配 11 E SLL 1 oeo 匹配 9IL i 1 oeo I i E SL 10i E SLL i 1 oeo 匹配 8SL i 1 oeo S I ifotherelse 01 statementif stmtelse partexp statement if stmt statement other if stmt if exp statementelse part else part elsestatement Exp 0 Exp 1 else part 解 1 分析表 if stmt if exp statementelse part 2020 2 18 北京化工大学信息科学与技术学院计算机系 89 2 分析if 0 if 1 otherelseother过程 缩写i 0 i 1 oeo 18eSL eo 匹配 131 SLL 1 oeo 匹配 17LL eo L eS 15SLL oeo S o 16oLL oeo 匹配 14 SLL oeo 匹配 ifotherelse 01 statementif stmtelse partexp statement if stmt statement other if stmt if exp statementelse part else part elsestatement Exp 0 Exp 1 else part 解 1 分析表 if stmt if exp statementelse part 2020 2 18 北京化工大学信息科学与技术学院计算机系 90 2 分析if 0 if 1 otherelseother过程 缩写i 0 i 1 oeo 19SL o S o 21L L 22 接受 20oL o 匹配 分析栈输入动作 ifotherelse 01 statementif stmtelse partexp statement if stmt statement other if stmt if exp statementelse part else part elsestatement Exp 0 Exp 1 else part 解 1 分析表 if stmt if exp statementelse part 2020 2 18 北京化工大学信息科学与技术学院计算机系 91 4 3 2 3leftRecursionRemovalandLeftFactoring消除左递归和提取左因子 leftRecursion左递归 exp e