[语法分析器.ppt

1 1 第五章 自顶向下语法分析方法 田丽芳 语法分析概览 练习：消除间接左递归 S ? Aa | b A ? Ac | Sd | ? for A: - Replace A ? Sd with A ? Aad | bd So, we will have A ? Ac | Aad | bd | ? - Eliminate the immediate left-recursion in A A ? bdA’ | A’ A’ ? cA’ | adA’ | ? So, the resulting equivalent grammar which is not left-recursive is: S ? Aa | b A ? bdA’ | A’ A’ ? cA’ | adA’ | ? 练习： 改造如下文法，判断改造后的文法是否是LL(1)文法？ lexp → atom | list atom →num | id list → (lexp_seq) lexp_seq → lexp_seq lexp | lexp 递归子程序法设计示例 例1：A ? aBb proc A { - match the current token with a, and move to the next token; - call B; - match the current token with b, and move to the next token; } 例2：A ? aBb | bAB proc A { case of the current token { a: - match the current token with a, and move to the next token; - call ‘B’; - match the current token with b, and move to the next token; b: - match the current token with b, and move to the next token; - call ‘A’; - call ‘B’; } } proc A { case of the current token { a: - match the current token with a, and move to the next token; - call B; - match the current token with e, and move to the next token; c: - match the current token with c, and move to the next token; - call B; - match the current token with d, and move to the next token; f: - call C } } 对输入串i+i*i的分析过程： stack input output # E i+i*i # E ? TE’ # E’T i+i*i # T ? FT’ # E’ T’F i+i*i # F ? i # E’ T’i i+i*i # 匹配 # E’ T’ +i*i # T’ ? ? # E’ +i*i # E’ ? +TE’ # E’ T+ +i*i # 匹配 # E’ T i*i # T ? FT’ # E’ T’ F i*i # F ?i # E’ T’i i*i # 匹配 # E’ T’ *i # T’ ? *FT’ # E’ T’ F * *i # 匹配 # E’ T’F i # F ? i # E’ T’i i # 匹配 # E’ T’ # T’ ? ? # E’ # E’ ? ? # # 接受 LL(1) parser算法（参考） LL(1) parser 输入 待分析单词流，以“#”结束。 输出 待分析单词流对应的最左推导。 分析栈 包含文法符号 栈底部为结束标