语法分析——自顶向下的分析。
重点与难点。
重点：自顶向下分析的基本思想，**分析器总体结构，**分析表的构造，递归下降分析法基本思想，简单算术表达式的递归下降分析器。
难点：first和follow集的求法，对它们的理解以及在构造ll(1)分析表时的使用。递归子程序法中如何体现分析的结果。
基本要求。掌握语法分析、2型文法的概念和自顶向下分析的基本思想，**分析器总体结构，**分析表的构造，递归下降分析法基本思想，简单算术表达式的递归下降分析器。
熟练掌握推导、first集和follow集的求法、消除左递归、提取左因子、ll(1)文法、文法的改写、递归子程序法、**分析法。
例题解析。例1求表达式文法的语法符号的first集和follow集表达式文法：e→te'e'→+te|εt→ft't'→*ft|εf→(e)|id
first(f)=
first(t)=first(f)=first(e)=first(t)=first(e')=first(t')=
first(+)first(*)first( (first( )first(id)=
follow(e
follow(e')=follow( e
follow(t) =first(e)∪follow(e)∪follow(efollow(t')=follow(t
follow(f) =first(t)∪follow(t)∪follow(t
例2消除下述文法的左递归。s→ac|ca→bb|bb→sa|a【解】先将间接左递归，变成直接左递归。
将b的定义代入a产生式得：a→sab|ab|b，将a的定义代入s产生式得： s→sabc|abc|bc|c采用引进新的非终结符的方法消除直接左递归：
s→abcs|bcs|css→abcs|ε
删除“多余的”产生式：a→sab|ab|b和b→sa|a
得到文法g[s]：s→abcs|bcs|css→abcs|ε
例3已知文法ｇ：s→(l|al→s,l|)
1）构造文法ｇ的**分析表。（2）若输入串为“（ａ请给出语法分析过程。【解】（１
1）求各非终结符的fisrt集和follow集：first(s) =first(sa }follow(sfollow(l) =follow(s2）**分析表：
sls→( ll→s , l
as→al→s , ll→)#
２）对输入串“（ａ的分析处理过程如表1所示。
表1对输入串“（ａ的分析过程。
步骤０１２分析栈＃ｓ＃l(＃l＃l, s＃l, a＃l,＃l＃）＃
输入串。所用产生式s→( l
l→s , ls→al→)
例4给定文法其中1)消除左递归；
2)计算改写后文法中各非终结符的first集和follow集；(3)构造改写后文法的**分析表；该文法是ll(1)文法吗？。【解】
1)消除左递归后的文法为：e→iaｅ＇ｅaｅ＇a→ia→ｄa→( e )
2)各非终结符的fisrt集和follow集first( e )
firstfirst( afollow( e ) #
followfollow( a3)改写后文法的**分析表：eｅ＇a
a→(e)#e→
e→ｉaｅ＇a→ｉ
a→ｄ＇→aｅ＇ｅaｅ＇ｅaｅ＇e→
**分析表中无多重入口，因此该文法是ll(1)文法。
例5 if语句的原始文法。
s→if e then s |if e then s else s |other
存在左因子if e then s,改写此文法消除左因子。.【解】引进非终结符ss'→εelse s提取左因子：s→if e then ss|other改写后的文法：
s→if e then ss|other
s'→εelse s
例6构造简单算术表达式的分析器【解】e的子程序(e→t(+t)*)procedure e;begin
t;ｔ的过程调用while lookhead='+dobegin当前符号等于＋时match(+)处理终结符＋tｔ的过程调用endend;lookhead：当前符号。
t的子程序(t→f(*f)*)procedure t;begin
f;f的过程调用while lookhead='*thenbegin当前符号等于＊时match('*处理终结符＊ff的递归调用endend;
f的子程序(f→(e)|id)procedure f;begin
if lookhead='(thenbegin当前符号等于（match('(处理终结符（e;e的递归调用。
match(')处理终结符）end
else if lookhead=id thenmatch(id)处理终结符idelse error出错处理end
主程序。begin
lookhead:=nexttoken;调词法分析程序ee的过程调用end
服务子程序。
procedure match(t:token);begin
if lookhead=tthen
lookhead:=nexttokenelse error出错处理程序end;
编译原理试题
编译原理模拟试题。班级姓名学号。1 20分 写出字母表 上语言l 的正规式，并画出接受该语言的最简dfa。2.10分 计算文法g m 的每个非终结符的first和follow集合，并判断该文法是否是ll 1 的，请说明理由。g mm tb t ba b db et d d 3.10分 写一个文法使其...
编译原理试题
东南大学。一 文法g1 e et t t tf f f fp p p e i1 试证明符号串tet i 是g1的一个句型 要求画出语法树 2 写出该句型的所有短语，简单短句和句柄。三 1 试写出一个上下文无关文法g3，它能产生配对的圆括号串 例如等，甚至包含0对括号 2 使用文法g3给出输入串 的自...
编译原理试题
1 最左简单子树的末端结点构成的符号串称为 2 若一个文法是递归的，则它产生的句子个数是 3 在通常的语法分析方法中，特别适用于表达式的分析。4 后缀式ab cd 可用表达式来表示。5 下面不是常见的中间语言表示形式是 6 文法分为四种类型，即0型 1型 2型 3型。其中3型文法是 7 表达式a b...