hh第5章 自顶向下语法分析方法

第5章自顶向下语法分析方法编译原理·语法分析技术专题Contents本章内容概览自顶向下语法分析的核心概念、方法与技术路线01语法分析基础与最左推导02文法转换与预处理技术03LL(1)文法与预测分析04FIRST集、FOLLOW集与SELECT集05递归与非递归分析方法CHAPTER01语法分析基础与最左推导理解语法分析器的角色、自顶向下分析策略及最左推导的核心机制CompilerFrontend语法分析器在编译流程中的角色语法分析器是编译前端的核心组件，位于词法分析与语义分析之间，负责将Token流依据文法规则构建为语法分析树。其分析方法分为自顶向下和自底向上两大流派，各有适用场景和技术特点。Token序列验证语法分析器接收词法分析器输出的Token序列，根据上下文无关文法规则判断输入是否构成合法程序结构语法分析树输出分析结果为语法分析树（SyntaxTree），为后续语义分析和中间代码生成提供结构化输入推导与归约方向自顶向下分析从根节点出发逐层推导构建子节点，自底向上分析从叶子节点归约合并至根节点实现策略差异自顶向下方法逻辑契合人类思维，便于手工实现；自底向上方法文法处理能力更强，通常依赖工具自动生成COMPILATIONSTRATEGY自顶向下与自底向上分析对比自顶向下和自底向上分析的核心差异在于语法树的构建方向：前者从根到叶推导，后者从叶到根归约。两种方法在实现便捷性、文法处理能力和工具依赖性上各有优劣，适用于不同的工程场景。自顶向下分析Top-Down01以起始符号为起点，采用深度优先策略逐层推导构建子节点，直至生成完整叶子节点序列02逻辑契合人类思维模式，可直接依据文法规则递归或迭代匹配输入Token，便于手工编码实现03推导过程清晰透明，开发者能直接跟踪从起始符号到输入序列的匹配路径，简化调试难度04主要局限是无法高效处理左递归文法，需通过文法改写消除左递归后才能应用自底向上分析Bottom-Up01从输入的终结符（叶子节点）入手，通过移进-归约操作逐步向上合并节点，最终完成根节点构建02文法处理能力更强，可支持左递归、二义性等更复杂的文法结构，适用范围更广03实现逻辑较为抽象，涉及状态转移表和移进-归约冲突处理，通常依赖Yacc/Bison等工具自动生成04更适合作为底层编译器工具链的实现机制，而非手工开发场景下的优先选择FormalLanguage&Automata最左推导与最右规约最左推导是自顶向下分析的核心操作机制，每步选择当前句型最左非终结符进行替换；其逆过程最右规约则是自底向上分析的基础。最左推导过程：E→E+E|E*E|(E)|id每步替换当前句型最左非终结符E，共6步完成推导01最左推导：每步推导中总是选择当前句型最左边的非终结符进行产生式替换，是自顶向下分析的核心操作02最右规约：最左推导的逆过程，从右向左逐步将输入串归约为起始符号，对应自底向上分析策略03最左句型：若S=*⇒α，则α称为当前文法的最左句型，是分析过程中的中间状态04语法分析树：推导过程形成树结构——根节点为起始符号，内部节点为非终结符，叶子节点为终结符或ε最左推导·LEFTMOSTDERIVATION最左推导示例：表达式文法通过表达式文法E→E+E|E*E|(E)|id推导id+(id+id)的完整过程，可以直观理解最左推导"每步替换最左非终结符"的操作机制，以及语法分析树的逐步构建过程。最左推导过程：目标串id+(id+id)步骤当前句型使用产生式被替换的非终结符1E+EE→E+EE(最左)2id+EE→idE(最左)3id+(E)E→(E)E(最左)4id+(E+E)E→E+EE(最左)5id+(id+E)E→idE(最左)6id+(id+id)E→idE(最左)经过6步最左推导，从起始符号E成功推导出目标串id+(id+id)CHAPTER02文法转换与预处理技术消除左递归与提取左公因子，为自顶向下分析扫清结构性障碍TOP-DOWNPARSING左递归问题：自顶向下分析的致命障碍左递归文法会导致递归下降分析器陷入无限循环，因为分析器在尝试匹配非终结符A时会不断递归调用自身而无法消耗任何输入符号。必须在使用自顶向下分析前通过文法转换彻底消除所有左递归。01直接左递归产生式形如A→Aα，非终结符A的产生式右部以A自身开头，一步即可产生左递归02间接左递归存在推导A⇒⁺Aα，经过两个或多个非终结符的传递后产生左递归，需两步以上推导才显现03无限循环陷阱递归下降分析器遇到左递归时，分析A的子程序会首先调用自身，形成死循环，无法向前消耗任何输入Token04消除策略消除左递归的本质是将左递归结构转换为等价的右递归结构，保持语言不变但改变推导方向COMPILERTHEORY·FORMALGRAMMAR消除直接左递归的标准算法消除直接左递归的核心公式将A→Aα|β转换为A→βA'和A'→αA'|ε，本质上是将左递归结构等价转换为右递归结构。01原始形式A→Aα₁|Aα₂|…|Aαₘ|β₁|β₂|…|βₙ其中αᵢ≠ε且βⱼ不以A开头A→Aα|β02转换结果A→β₁A'|β₂A'|…|βₙA'A'→α₁A'|α₂A'|…|αₘA'|ε引入新非终结符A'引入A'03转换本质将左递归(A→Aα)等价转换为右递归(A'→αA')，保持生成语言不变，仅改变推导方向。左递归→右递归04经典示例E→E+T|T⇒E→TE',E'→+TE'|εT→T*F|F⇒T→FT',T'→*FT'|εE→TE'COMPILERDESIGN示例：表达式文法的左递归消除经典表达式文法E→E+T|E-T|T、T→T*F|T/F|F、F→(E)|id包含多处直接左递归，通过标准算法逐一消除后得到等价的右递归文法，为后续构建LL(1)预测分析器奠定基础。表达式文法消除直接左递归的完整过程原始产生式转换后主产生式新增非终结符产生式E→E+T|E-T|TE→TE'E'→+TE'|-TE'|εT→T*F|T/F|FT→FT'T'→*FT'|/FT'|εF→(E)|idF→(E)|id（无左递归，无需转换）三组产生式逐一消除左递归，引入E'和T'两个新非终结符，语言等价性得到保证编译原理·语法分析消除间接左递归的方法间接左递归通过多个非终结符的传递推导形成，需先按顺序将前方非终结符的产生式代入后方，将间接左递归暴露为直接左递归，再使用标准算法消除。01📋间接左递归示例S→Aa|b，A→Ac|Sd|ε，S经A间接产生左递归推导链：S⇒Aa⇒Ac…⇒Sd…a，形成循环依赖02🎯消除策略按非终结符排序，将排序靠前的定义代入靠后的产生式中核心思想：通过代入暴露隐藏的左递归结构03🔄代入操作将S的定义代入A的产生式，得A→Ac|Aad|bd|ε此时A出现直接左递归，可应用标准消除算法04✅最终结果消除A的直接左递归得A→bdA'|εA'A'→cA'|adA'|ε，完成间接左递归消除GRAMMARTRANSFORMATION提取左公因子LeftFactoring当非终结符的多个产生式共享相同前缀时，分析器无法在有限前瞻下做出正确选择。提取左公因子通过改写产生式推迟决策，等读入足够多的输入获得足够信息后再做出正确的分支选择。PROBLEM问题场景A→αβ₁|αβ₂，两个产生式共享前缀α，分析器看到α对应的输入时无法决定选择哪个分支A→αβ₁|αβ₂METHOD转换方法提取公共前缀α，引入新非终结符A'，改写为A→αA'，A'→β₁|β₂，将决策推迟到匹配α之后A→αA',A'→β₁|β₂RECURSION多次提取若提取后A'的产生式仍存在公共前缀，需递归进行左公因子提取，直至所有分支首符号不同递归至无公因子EXAMPLE经典示例S→aAd|aBe转换为S→aS'，S'→Ad|Be，分析器匹配a后再根据下一个符号选择分支S→aS',S'→Ad|Be编译原理·文法改写文法改写的语义保持原则消除左递归时必须使用标准转换公式，不能简单调换符号位置，否则可能破坏运算符的结合性等语义规则。以减法表达式为例，随意调换会导致左结合变为右结合，计算结果发生错误。错误做法：简单调换符号位置01原始文法EXPR→EXPR'-'DIGIT|DIGIT存在左递归，若改为EXPR→DIGIT'-'EXPR|DIGIT02表达式3-2-1的推导变为3-(2-1)=2，减法变成右结合，违反数学运算语义，结果错误3-(2-1)=2

✗错误正确做法：标准消除左递归公式01按标准公式改写：EXPR→DIGITEXPR'，EXPR'→'-'DIGITEXPR'|ε02表达式3-2-1的推导保持(3-2)-1=0，减法维持左结合性，语义正确(3-2)-1=0

✓正确CHAPTER03LL(1)文法与预测分析掌握LL(1)文法的定义、判定条件及其在确定性语法分析中的核心地位FORMALLANGUAGE&AUTOMATALL(1)文法的定义与命名含义LL(1)文法的命名精确描述了其分析策略：从左向右扫描、产生最左推导、1个符号前瞻。其核心要求是同一非终结符的不同产生式的SELECT集互不相交，保证分析器能无回溯地做出确定性决策。L₁Left-to-right扫描从左向右逐个读取输入串中的Token，按顺序扫描，不回头、不跳跃，保证分析过程与输入流方向一致。这种扫描方式符合常规阅读习惯，也是大多数编程语言词法分析的标准处理方式。L₂Left-most最左推导每步推导始终替换当前句型中最左边的非终结符，按固定顺序逐步构建语法树，保证推导过程唯一确定。最左推导与递归下降分析器的函数调用结构天然对应，便于手工实现。1Lookahead=1每步决策仅需向前看1个输入符号即可确定应选用的产生式，无需回溯，分析效率高且实现简洁。单个符号的预读需求使得预测分析表结构紧凑，内存占用小，适合嵌入式场景。SELECT集不相交对任意A→α|β，要求SELECT(α)∩SELECT(β)=∅，确保分析器在每个决策点能无歧义地选择唯一产生式。这是LL(1)文法的充要条件，也是构造预测分析表的数学基础。FormalLanguage&CompilerLL(1)文法的判定条件LL(1)文法的三个判定条件从不同角度确保分析决策的唯一性：不同时推导空串、空串推导与FOLLOW集不冲突、SELECT集互不相交。不满足条件的文法需转换或改用更强分析方法。01禁止同时推导空串——A→α和A→β不能同时推导出空串ε，即同一非终结符至多一个产生式可以推导出ε02空串推导与FOLLOW集不冲突——若α=>*ε，则FIRST(β)∩FOLLOW(A)=∅，确保ε产生式与其他产生式不冲突03SELECT集互不相交——SELECT(A→α)∩SELECT(A→β)=∅，保证每个输入符号至多对应一个可用产生式04不满足时的处理——可通过消除左递归、提取左公因子转换文法；若仍不满足则需LL(k)或LR分析方法CHAPTER04FIRST集、FOLLOW集与SELECT集掌握三大关键集合的定义、计算规则及其在预测分析表构建中的应用编译原理·自顶向下分析FIRST集：首终结符集合FIRST(α)收集了从符号串α能推导出的所有串的首终结符，是预测分析器判断应选用哪个产生式的核心依据。其计算遵循终结符直接加入、非终结符逐层传递、空串条件延伸三条基本规则。01定义FIRST(X)={a|X⇒*a…}，即从X推导出的所有串的首终结符构成的集合；若X⇒*ε则ε∈FIRST(X)02规则一（终结符）若X为终结符，则FIRST(X)={X}，终结符的FIRST集只包含自身03规则二（非终结符）若X→Y₁Y₂…Yₖ，将FIRST(Y₁)的非ε元素加入FIRST(X)；若Y₁⇒*ε则继续加入FIRST(Y₂)的非ε元素，依次类推04规则三（空串传播）若所有Yᵢ都能推导出ε（i=1..k），则将ε加入FIRST(X)；若X→ε则ε∈FIRST(X)CompilerTheoryFIRST集计算示例以消除左递归后的表达式文法为例，FIRST集从底层符号逐层上传，体现迭代应用与空串传播。表达式文法各符号的FIRST集计算结果文法符号FIRST集计算依据F{(,id}F→(E)|id，首符号为(和idT'{*,/,ε}T'→*FT'|/FT'|ε，首符号为*和/，且可推导εT{(,id}T→FT'，FIRST(T)=FIRST(F)={(,id}E'{+,-,ε}E'→+TE'|-TE'|ε，首符号为+和-，且可推导εE{(,id}E→TE'，FIRST(E)=FIRST(T)={(,id}FIRST集从底层符号向上逐层计算，非终结符的FIRST集由其产生式右部首符号决定FormalLanguage·ParsingFOLLOW集：后继终结符集合FOLLOW(A)收集了在句型中可能紧跟在非终结符A后面的终结符，是判断何时选用ε产生式的关键依据。其计算依赖FIRST集结果，需结合产生式上下文和起始符号的结束标记进行迭代推导。01定义：FOLLOW(A)={a|S=*⇒...Aa...}，即在某个句型中紧跟在A之后的终结符集合，仅对非终结符定义02起始符号规则：将输入结束标记$加入FOLLOW(S)，S为文法起始符号03中间位置规则：若A→αBβ，将FIRST(β)中除ε外的所有元素加入FOLLOW(B)04末尾位置规则：若A→αB或A→αBβ且β=*⇒ε，则将FOLLOW(A)的全部元素加入FOLLOW(B)COMPILER·FORMALLANGUAGESFOLLOW集计算示例FOLLOW集的计算依赖已完成的FIRST集结果，需从起始符号出发，结合产生式右部的上下文位置反复应用三条规则进行迭代，直至所有集合不再变化为止。表达式文法各非终结符的FOLLOW集非终结符FOLLOW集计算依据E{$,)}E为起始符号加入$；F→(E)中E后为)E'{$,)}E→TE'中E'在末尾，FOLLOW(E')=FOLLOW(E)T{+,-,$,)}E→TE'中FIRST(E')含+、-、ε，ε传播FOLLOW(E')T'{+,-,$,)}T→FT'中T'在末尾，FOLLOW(T')=FOLLOW(T)F{*,/,+,-,$,)}T→FT'中FIRST(T')含*、/、ε，ε传播FOLLOW(T')FOLLOW集通过产生式上下文和ε传播规则迭代计算，反映非终结符在句型中可能出现的后继环境FORMALLANGUAGE&AUTOMATASELECT集：预测分析的选择依据SELECT集综合FIRST与FOLLOW集信息，是LL(1)预测分析表的构建依据，要求同一非终结符各产生式SELECT集互不相交。01定义与别名SELECT(A→α)表示选用产生式A→α时所期望看到的输入符号集合，也称预测集（PredictSet）。PredictSet02α不能推导εSELECT(A→α)=FIRST(α)，直接取右部首部的终结符集合，无需考虑后继符号。FIRST(α)03α能推导εSELECT(A→α)=(FIRST(α)−{ε})∪FOLLOW(A)，将ε情况映射到后继符号集合。∪FOLLOW(A)04LL(1)判定条件对A的所有产生式，SELECT(αᵢ)∩SELECT(αⱼ)=∅（i≠j），确保预测选择唯一确定。∩=∅LL(1)GRAMMARSELECT集计算与LL(1)验证示例通过计算E'三个产生式的SELECT集并验证其互不相交，完整展示了从FIRST集、FOLLOW集到SELECT集的计算链条，以及LL(1)文法判定的实际操作流程。E'产生式的SELECT集计算与LL(1)验证产生式FIRST集SELECT集LL(1)验证E'→+TE'{+}{+}✓E'→-TE'{-}{-}✓E'→ε{ε}{$,)}✓三个SELECT集{+}、{-}、{$,)}两两不相交，E'的产生式满足LL(1)条件。Chapter05递归与非递归分析方法从递归下降分析器到基于栈的预测分析器，掌握两种实现路径的设计与比较COMPILERDESIGN递归下降分析器的设计原理递归下降分析器为每个非终结符编写一个递归函数，函数的内部逻辑直接映射文法产生式的选择与匹配过程。01核心思想为文法中每个非终结符A编写递归函数parse_A()，函数体实现A的所有产生式分支选择02终结符处理遇到终结符时调用match(a)函数，验证当前Token是否匹配，匹配则前进，否则报错03非终结符处理遇到非终结符B时直接调用parse_B()，形成递归调用链，模拟语法树深度优先构建04分支选择根据当前Token（Lookahead）与各产生式SELECT集的交集，选择并执行对应的产生式分支IMPLEMENTATION递归下降分析器伪代码实现递归下降分析器的伪代码直接映射文法产生式：每个非终结符对应一个函数，产生式的SELECT集决定分支条件，右部符号序列决定函数体内的调用顺序。01parse_E()函数调用parse_T()处理T非终结符调用parse_E_prime()处理E'非终结符函数体仅两行调用，对应产生式E→TE'02parse_E_prime()函数LOOKAHEAD∈{+}match('+'),parse_T(),parse_E_prime()，对应E'→+TE'LOOKAHEAD∈{−}match('-'),parse_T(),parse_E_prime()，对应E'→−TE'LOOKAHEAD∈{$,)}匹配ε，不消耗输入直接返回OTHERWISE调用error()报告语法错误ParserArchitecture非递归预测分析器的核心结构非递归预测分析器用显式栈和预测分析表替代递归调用，通过查表-弹栈-压栈的循环操作完成语法分析。相比递归方式，它具有更高的运行效率和更规范的错误处理机制，是工业级编译器常用的实现方案。分析栈Stack初始压入起始符号S和结束标记$，自顶向下分析过程中存放待匹配的文法符号序列S→$预测分析表M[A,a]二维表格，行为非终结符，列为终结符，M[A,a]存放当栈顶为A且输入为a时应选用的产生式M[A,a]输入缓冲区存放词法分析器输出的Token序列，以$结尾，指针从左向右逐个扫描Token→核心循环查看栈顶X和输入a：X=a则弹出并前进；X为非终结符则查表M[X,a]弹X压右部；直到栈和输入均为$查表·弹栈·压栈LL(1)PREDICTIVEPARSING预测分析表的构建方法预测分析表通过遍历所有产生式，将每个产生式填入其SELECT集对应的表格位置来构建。若某个单元格被填入多个产生式则文法非LL(1)；空白单元格标记为错误条目，用于运行时语法错误检测。表达式文法的LL(1)预测分析表非终结符id+-*/()$EE→TE'E→TE'E'E'→+TE'E'→-TE'E'→εE'→εTT→FT'T→FT'T'T'→εT'→εT'→*FT'T'→/FT'T'→εT'→εFF→idF→(E)每个单元格至多包含一个产生式，证明该文法是LL(1)文法；空白单元格为错误条目LL(1)PARSINGDEMO预测分析器工作流程演示以输入串id+id$为例，完整展示非递归预测分析器的逐步操作过程：查表确定产生式、弹栈压栈替换非终结符、匹配消耗终结符。每一步都由栈顶符号和当前输入唯一确定，体现LL(1)分析的确定性特征。输入串id+id$的预测分析过程步骤分析栈（顶→底）剩余输入操作1E$id+id$查M[E,id]，弹出E，压入E′T2TE′$id+id$查M[T,id]，弹出T，压入T′F3FT′E′$id+id$查M[F,id]，弹出F，压入id4idT′E′$id+id$匹配id，弹出id，输入前进5T′E′$+id$查M[T′,+]=ε，弹出T′6E′$+id$查M[E′,+]=+TE′，压入E′T+分析器通过查表→弹栈→压栈→匹配的循环，逐步消化输入，展现确定性LL(1)分析的完整流程ErrorRecovery预测分析器的错误处理与恢复非递归预测分析器在遇到分析表空白单元格或终结符不匹配时触发错误处理。恐慌模式通过跳过输入至同步符号实现快速恢复，短语级恢复则在错误条目中嵌入定制化恢复例程，两者结合可有效提升分析器的鲁棒性。01分析表空白触发栈顶为非终结符A，当前输入为a，但M[A,a]为空，说明输入符号a不应出现在此位置。这是预测分析器最常见的错误触发场景，表明当前输入与文法预期不符。