当前位置：文档之家 › 【习题答案】第04章 自顶向下的语法分析

【习题答案】第04章 自顶向下的语法分析

  • 格式：pdf
  • 大小：404.62 KB
  • 文档页数：4

下载文档原格式

  / 4

合集下载

第4章 自顶向下的语法分析

第4章 自顶向下的语法分析

6
分析中出现的问题2：回溯问题
从各种可能的选择中随机挑选一种， 并希望它是正确的。 如果以后发现它是错误的，必须退 回去，再试另外的选择这种方式称为回 溯。 回溯代价极高，效率很低。
7
在自上而下的分析方法中如何选择使 用哪个产生式进行推导？ 假定要被替换的最左非终结符号是B， 且有n条规则：B→A1|A2|…|An，那么如何 确定用哪个右部去替代B？ 从文法的开始符号出发，如何根据当前 的输入符号（单词符号）唯一地确定选用哪 个产生式替换相应非终结符往下推导，或构 造一棵相应的语法树。
8
§4.2 FIRST和FOLLOW集合的构造
9
例1:输入串w=pccadd是否是合法的句子？
G：S→pA|qB A→cAd|a B→dB|b
S=>pA=>pcAd=>pccAdd=>pccadd 总结：本题中对于一个非终结符，存在若干 个候选式，即产生式形如：P→α1|α2|……|αn 每个候选式的第一个字符都是终结符， 且都不相同。这时可直接选用与当前输入符 号相同的那个候选式来替换P。
42
3. 若X为一非终结符，则查分析表M。 若M[X，a]中为A—产生式，将A自栈 顶弹出，将产生式右部符号串按逆序逐 一推入栈中；当产生式为A时，则只将 A→ε弹出即可。若M[X，a]中为空,则调 用出错处理程序。
43
算法实现
当前字符匹 配成功。 要对栈顶的 非终结符进 行替换。
44
初始化
注意一 定要逆 序入栈。
48
49
通过表4-9可以看到，每个非终结符对应 产生式的各个候选式的交集如下：
可以验证，此文法是LL(1)文法。
50
递归下降语法分析程序如下：

编译技术复习题答案

编译技术复习题答案

第一章：编译系统概述一．单项选择题1．编译程序前三个阶段完成的工作是〔C〕。

A．词法分析, 语法分析和代码优化B．代码生成, 代码优化和词法分析C．词法分析, 语法分析, 语义分析和中间代码生成D．词法分析, 语法分析和代码优化2．编译程序绝大多数时间花在〔D〕上。

A．出错处理 B．词法分析 C．目标代码生成D．表格管理3．编译程序是对〔C〕。

A．汇编程序的翻译 B．高级语言程序的说明执行C．高级语言的翻译 D．机器语言的执行4．在运用高级语言编程时，首先可通过编译程序发觉源程序的全部〔A〕错误。

A．语法 B．语义 C．语用 D．运行二．填空题1．编译程序首先要识别出源程序中每个(单词)，然后再分析每个(句子)并翻译其意义。

2．通常把编译过程分为分析前端及后端两大阶段。

词法, 语法和语义分析是对源程序的(分析)，中间代码生成, 代码优化及目标代码的生成那么是对源程序的(综合)。

3．对编译程序而言，输入数据是(源程序)，输出结果是(目标程序)。

4．对以下错误信息，请指出可能是编译的哪个阶段〔词法分析, 语法分析, 语义分析,代码生成〕报告的。

〔1〕 else 没有匹配的if 〔语法分析〕〔2〕数组下标越界〔语义分析〕〔3〕运用的函数没有定义〔语法分析〕〔4〕在数中出现非数字字符〔词法分析〕5．假如编译程序生成的目标程序是机器代码程序，那么源程序的执行分为两大阶段：〔编译阶段〕和〔运行阶段〕。

假如编译程序生成的目标程序是汇编语言程序，那么源程序的执行方式分成三个阶段：〔编译阶段〕〔汇编阶段〕和〔运行阶段〕。

6．编译程序在其工作过程运用最多的数据构造是〔表〕，它记录着源程序中各种信息，以便查询或修改，在这些〔表〕中，尤以〔符号表〕最重要，它的生存期最长，运用也最频繁。

三．简述题：1．编译程序的工作分为那几个阶段答：词法分析, 语法分析和语义分析是对源程序进展的分析(称为编译程序的前端)，而中间代码生成, 代码优化和代码生成三个阶段合称为对源程序进展综合(称为编译程序的后端)，它们从源程序的中间表示建立起和源程序等价的目标程序。

4第四章 自顶向下语法分析法1

4第四章 自顶向下语法分析法1
回溯分析程序的特点：功能强大，但非常慢，一般都在指 数的数量级，所以对于实际的编译器并不合适。
两类预测分析算法： （1）递归下降分析（recursive-descent parsing）很常 用，且最适合于手写的分析程序最为适合。 （2）LL(1)分析（ LL(1) parsing）中第1个“L”指由左向 右地处理输入；第2个“L”指利用最左推导进行分析；括 号中的数字1仅向前查看一个符号进行预测分析。LL(k)分 析利用向前查看k个符号进行预测分析。
+
/\
+5
/\
34 构造过程： （1）对每个运算都实施语法树的生成 （2）对每个递归函数加上当前语法树树根的返回
syntaxTree exp ( )
{
syntaxTree temp, newtemp;
temp = term ( ) ;
while (token == ‘+’ || token = ‘-’){
• 请编写以下表达式文法的递归下降分析程序。
exp → exp addop term | term addop → + | term → term mulop factor | factor mulop → * factor → ( exp ) | number
识别factor → ( exp ) | number的递归下降子程序如下： void factor( ) {
G[E]={E→E+T|T, T→T*F|F, F→(E)|i }，
符号串i+i*i自顶向下的分析过程：
• 自顶向下的分析程序有两类： （1）预测分析程序（predictive parser）试图利用超前 查看一个或多个记号来预测出该选择哪条规则。 （2）回溯分析程序（backtracking parser）则试着分析 所有的可能输入，当一种可能失败时就要求输入中备份任 意数量的字符。

编译原理课后习题答案

编译原理课后习题答案

5-01.自底向上的语法分析方法的基本思想是：从给定的终极符串开始，根据文法的规则一步一步的向上进行
直接归约，试图归约到文法的 开始符号 。
5-02.自底向上的语法分析方法的基本思想是：从输入串入手，利用文法的产生式一步一步地向上进行 直接
归约 ，力求 归约 到文法的 开始符号 。
向貌似句柄的符号串后查看0个输入符号 。
5-05.在SLR（1）分析法的名称中，S的含义是 简单的 。
6-01.所谓属性文法是 一个属性文法是一个三元组：A＝（G，V，F），一个上下文无关文法G；一个属性的
有穷集V和关于属性的断言或谓词的有穷集F。每个断言与文法的某产生式相联。
8-01.符号表中的信息栏中登记了每个名字的 属性和特征等有关信息 ，如类型、种属、所占单元大小、地址
等等。
8-02.一个过程相应的DISPLAY表的内容为 现行活动记录地址和所有外层最新活动记录的地址 。
9-01.一个过程相应的DISPLAY表的内容为 现行活动记录地址和所有外层最新活动记录的地址 。
1-29．按逻辑上划分，编译程序第二步工作是 C 。
A. 语义分析 B. 词法分析 C. 语法分析 D. 代码优化
c.机器执行效率 d.是否生成目标代码
1-12.汇编程序是将 a 翻译成 b ,编译程序是将 c 翻译成 d .
a.汇编语言程序 b.机器语言程序 c.高级语言程序
d. a 或者 b e. a 或者 c f. b 或者 c
1-21.编译程序是一种常用的 b 软件.
a. 应用 b. 系统
1-22.编写一个计算机高级语言的源程序后,到正式上机运行之前，一般要经过 b 这几步.

编译原理 第4章 语法分析—自顶向下分析

编译原理 第4章 语法分析—自顶向下分析

例 S::=aABbcd|ε，A::=ASd|ε，B::=SAh|eC|ε，
C::=Sf|Cg|ε，求此文法的每一个非终结符号的
FOLLOW集。
解：FOLLOW(S)={#}∪FIRST(d) ∪(FIRST(Ah)-{ε}) ∪FIRST(f)
={#}∪{d}∪{a,d,h}∪{f} = {a,d,h,f,#}
4)若对于一切1≤i≤n，ε∈FIRST(Xi)，则将ε符号加 进FIRST(α)。
例4-1(P62) 有文法： E→TE′ E′→+TE′ E′→ε T→FT′ T′→*FT′ T′→ε F→(E)|i 求文法中非 终结符号以及各 产生式右部符号 串的FIRST集。
解：该文法的非终结符号有E、E′、 T、T′和F。 FIRST(E)=FIRST(TE′) =FIRST(FT′E′)={ ( ，i } FIRST(+TE′)={ + } FIRST(ε)={ε} FIRST(E′)=FIRST(+TE′) ∪FIRST(ε)={+ ，ε} FIRST(T)=FIRST(FT′)={ ( ，i } FIRST(*FT′)={ * } FIRST(T′)=FIRST(*FT′) ∪FIRST(ε)={* ，ε} FIRST((E))={ ( } FIRST(i)={ i } FIRST(F) =FIRST((E)) ∪FIRST(i)={( ，i}
分析法算符优先分析法简单优先分析法优先分析法自底向上带回溯递归下降分析法分析法不带回溯自顶向下语法分析lr回溯示例41p61自顶向下的分析方法就是从文法的开始符号出发按最左推导方式向下推导试图推导出要分析的输开始符号输入符号串自底向上的分析方法从输入符号串开始按最左归约方式向上归约到文法的开始符号

04 语法分析(1) _ 概述(含 消除左递归)

04 语法分析(1) _ 概述(含 消除左递归)

消除间接左递归的方法：
(1) 把间接左递归文法改写为直接左递归文法；
(2) 用消除直接左递归的方法改写文法。
下面给出一个消除文法所有左递归性的算法，该算
法对文法的要求是：文法不含回路（形如ＰＰ的
推导），且不含以ε为右部的产生式。
通用算法
• 阅读 P84 算法4.1
①把G的非终结符按任意顺序排列，如A1,…,An ②for(i=1；i<=n；i++)
0 1
q0
1
q1

q2
【定义】一个下推自动机可定义为一个7元组：
PDA M=(Q, , , q0, Z0, F, )
其中： ① Q是有限状态集； ② 是输入符号集； ③ 是栈符号集； ④ q0Q，称为起始状态； ⑤ Z0，称为栈起始符； ⑥ FQ，称为接受状态集； ⑦ 是转移函数，定义域为Q×({ε})×，且表示由 “当前状态qi、输入符号a和栈顶符号x决定PDA的转 移动作”。值域为Q×*，指明下推自动机的动作结 果包括“状态转移和栈操作”。
例4.6
设有文法G： I→I0 | Ia | Ib | a | b
对左递归文法G改写后的文法G'为 I → aI' | bI' I ' → 0I' | aI' | bI' |ε
习题 4.8
将下面的左递归文法G(S)改为非左递归的。
S → SaP|Sf |P P → QbP|Q Q → cSd|e 【解】 S → PS’ S’→ aPS’| f S’|ε P → QbP|Q Q → cSd|e
第4章 语法分析
—— 自顶向下分析法
思考题
上次课所留问题：
设计例3-3的词法分析程序。

编译原理第4章习题答案


2）文法： S SS | SS* | a 输入串：aaa*a++ 自底向上语法分析过程：
c.消除左递归：S->aS’ S’->SAS’|Ɛ A->+|*
代入
S->aS’ S’->aS’AS’|Ɛ A->+|*
d.得到的文法适用于自顶向下的语法分析吗？ 适用。因为文法中不存在左公因子，也不存在左递归
4.4.3 S->SS+|SS*|a
FIRST(S)={a}
因为S是起始符号，把{$}加入到Follow(S)中。 对于S->SS+的第一个S，把First(S+) = {a}加入到Follow(S)中。 对于S->SS*的第一个S，把First(S*) = {a}加入到Follow(S)中。 对于S->SS+的第二个S，把First(+) = {+}加入到Follow(S)中。 对于S->SS*的第二个S，把First(*) = {*}加入到Follow(S)中。 所以，FOLLOW(S)={a,+,*,$}
S A| B A AA | E0E （A是0比1多的串） B BB | E1E （B是1比0多的串） E 0E1E | 1E0E | （E是0和1的个数相等的串）
5）所有由0和1组成的且其中不包含子串011的串的集合。
S AB A 1 A | B 0 B | 01 B |
6）所有由0和1组成的形如xy的串的集合，其中 x y 且x和y等长。 S AB | BA A XAX | 0 （A是奇数长度，中间为0的串） B XBX | 1 （B是奇数长度，中间为1的串） X0|1

第四章 语法分析-自顶向下分析方法



自顶向下分析的条件
产生式A→被选择的条件是： 当前的输入符属于predict(A→)。 至多一个产生式被选择的条件是： predict(A→k) predict(A→j )=，当k j 自顶向下分析方法的条件： predict(A→k) predict(A→j )=，当k j
作用：可以根据当前的输入符号是属于哪个产生 式右部的首符集而决定选择相应产生式进行推导
文法G3[S]: S aA | d A bAS | 输入串W=abd。自顶向下的推导过程为: S S aA a A abAS abS b A S abd d 相应的语法树为：
Follow集的定义
else
end;
err( )
4.3 LL分析方法
LL(1)是LL(k)的特例,其中的k则表示向前看k 个符号。 LL(1)方法和递归下降法属于同一级别的自顶 向下分析法，但有一些区别.

递归下降法对每个非终极符产生子程序，而LL(1)方 法则产生LL分析表； 递归下降法能判断每个产生式的结束，而LL(1)方法 则不能； 递归下降法分析法不用符号栈，而LL(1)方法则用符 号栈。
计算First(X)集
对每一文法符号X计算First(X) 若XVT,First(X)={X} 若 X V N则 First(X)={a| Xa…PSet,aVT} 若XVN,且有产生式X,则 First(X) 若XVN,有产生式XY1Y2…Yn，且Y1,Y2,…,Yi VN 当Y1,Y2,…,Yi-1* ， 则First(Y1)-{},First(Y2)-{},… First(Yi-1)-{}, First(Yi)都包含在First(X)中。 当Yi * (i=1,2,…n), 将{}并入First(X) 中。

《计算机网络自顶向下》课后习题答案(第四章_中文版)

4复习题1.网络层的分组名称是数据报.路由器是根据包的IP地址转发包;而链路层是根据包的MAC地址来转发包.2.数据报网络中网络层两个最重要的功能是:转发,选路.虚电路网络层最重要的三个功能是:转发,选路,和呼叫建立.3.P200 转发是当一个分组到达路由器的一条输入链路时,该路由器将该分组移动到适当的输出链路.选路是当分组从发送方流向接收方时,网络层必须决定这些分组所采用的路由或路径.4.是,都使用转发表,要描述转发表,请参考4.2节.在虚电路网络中，该网络的路由器必须为进行中的连接维持连接状态信息。

每当跨越一台路由器则创建一个新连接，一个新的连接项必须加到该路由器转发表中；每当释放一个连接，必须从该表中删除该项。

注意到即使没有VC号转换，仍有必要维持连接状态信息，该信息将VC号与输出接口号联系起来。

每当一个端系统要发送分组时，它就为该分组加上目的地端系统的地址，然后将该分组推进网络中。

完成这些无需建立任何虚电路。

在数据报网络中的路由器不维护任何有关虚电路的状态信息。

每个路由器有一个将目的地址影射到链路接口的转发表；当分组到达路由器时，该路由器使用该分组的目的地址在该转发表中查找适当的输出链路接口。

然后路由其将该分组项该输出链路接口转发。

虽然在数据报网络中不维持连接状态信息，它们无论如何在其转发表中维持了转发状态信息。

在数据报网络中的转发表是由选录算法修改的，通常每1到5分钟左右更新转发表。

在虚电路网络中，无论何时通过路由器拆除一条现有的连接，路由器中的转发表就更新。

5.P202 单个分组:确保交付;具有延时上界的确保交付.分组流:有序分组交付;确保最小带宽;确保最大时延抖动.因特网的网络层不提供这些服务.ATM的CBR（恒定比特率）服务同时提供确保交付和计时.ABR（可用比特率）不提供该假想服务.6.交互式实时多媒体应用,如:IP电话和视频会议.这些应用都得益于ATM的CBR服务的实时性.7.正是由于有影子拷贝,在每个输入端口的转发都由本地决定,而不用调用中心选路处理器.这种分散的转发方式避免了在路由器的某一个节点出现转发处理的瓶颈.8.P211 (1)经内存交换:在输入和输出端口之间的交换是在CPU控制下完成的.输入与输出端口的作用就像在传统操作系统中的I/O设备一样.一个分组到达一个输入端口,该端口会先通过中断方式向选路处理器发出信号.于是,该分组就被拷贝到处理器内存中.选路处理器从分组首部中取出目的地址,在转发表中找出适当的输出端口,并将该分组拷贝到输出端口的缓存中.(2)经一根总线交换:输入端口经一根总线将分组直接传送到输出端口,不需要选路处理器的干预.由于总线是共享的,故一次只能有一个分组通过总线传送.(3)经一个互联网络交换:使用一个纵横的网络,是一个由2n条总线组成的互联网络,它将n个输出端口和n个输入端口连接,一个到达某个端口的分组沿着连到输出端口的水平总线穿行,直至该水平总线与连到所希望的输出端口的垂直总线之交点.9.P213 如果在输入端口因为交换结构速率慢而引起队列长度的加大,最终将路由器的缓存空间耗尽,就会出现“分组丢失”.如果交换结构速率大于线路速率的n倍(n是输入端口的数量)就可以消除分组丢失的问题. 10.因为输出线速率慢而导致输出端队列长度加大，最终将耗尽输出端口的存储空间，在这样的情况下，分组就被丢弃了。

编译原理第3版完整答案

编译原理第3版完整答案编译原理是计算机科学与技术领域中非常重要的一门课程，它研究的是如何将人类编写的高级程序转化为计算机能够理解和执行的机器语言指令。

编译原理第3版是一本经典的教材，本文将全面介绍该教材中的所有章节，并提供完整的答案。

第1章引论1.1 编译器和解释器的基本概念编译器和解释器是两种将高级语言转化为机器指令的方法。

编译器将整个程序作为输入，分析和翻译整个程序，将结果存储在一个可执行的目标文件中。

解释器则逐行解释源程序，一边解释一边执行。

1.2 编译器结构编译器可以分为前端和后端两个主要组成部分。

前端负责源程序的分析和翻译，包括词法分析、语法分析和语义分析；后端则负责将中间表示转换为目标机器代码。

1.3 语言处理器的实现方式语言处理器的实现方式可以分为两种：解释执行和编译执行。

解释执行是指将源程序逐条解释执行；编译执行则是将源程序先编译为目标代码，再执行。

第2章词法分析2.1 词法单元、词法规则和词法分析器词法分析是编译器中的第一个阶段，它将源程序分割为一个个的词法单元。

词法规则定义了词法单元的语法和形式，词法分析器根据这些规则识别出词法单元。

2.2 正则表达式和有限自动机正则表达式是一种描述字符串模式的语言，它可以用来描述词法规则。

有限自动机是一种用于识别正则表达式的计算模型。

2.3 正则表达式到有限自动机的转换通过将正则表达式转换为等价的有限自动机，可以实现正则表达式的匹配。

第3章语法分析3.1 上下文无关文法和语法分析器语法分析是编译器中的第二个阶段，它根据语法规则将词法单元组成的序列转换为语法分析树。

上下文无关文法是一种用于描述语法规则的形式化语言。

3.2 自顶向下语法分析方法自顶向下语法分析方法从根节点开始构建语法分析树，逐步展开每个非终结符，直到达到叶子节点。

3.3 自底向上语法分析方法自底向上语法分析方法从词法单元开始反向推导出语法分析树的构造过程。

第4章语义分析4.1 属性文法和语义分析器语义分析是编译器中的第三个阶段，它对语法分析树中的节点进行语义处理和类型检查。

  1. 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
  2. 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
  3. 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。

（2）对输入串 “ （a， ） ”的分析处理过程如下表所示。 步骤 0 1 2 3 4 5 6 7 8 2. 分析栈 ＃S ＃L ( ＃L ＃L , S ＃L , a ＃L, ＃L ＃） ＃ 输入串 （a， ）＃ （a， ）＃ a， ）＃ a， ）＃ a， ）＃ ， ）＃ ）＃ ）＃ ＃ 所用产生式 S→(L L→ S, L S→a
L→ )
给定文法 G＝（ ｛ i，d，'('，')' ｝ ， ｛E，A｝ ， E， P ）, 其中 P： E→ ｉA E→ EA A→ i A→ d A→ ( E )
(1)消除左递归； (2)计算改写后文法中各非终结符的 FIRST 集和 FOLLOW 集； (3)构造改写后文法的预测分析表；该文法是 LL(1) 文法吗?
共 4 页，第 1 页
《编译原理》 课后练习参考答案
第 04 章 自顶向下的语法分析
【解】 (1) 消除左递归后的文法为: E → iAE＇ E＇→ | AE＇ A → i A → d A → (E) (2) 各非终结符的 FISRT 集和 FOLLOW 集 FIRST( E ) =｛i｝ FIRST( E＇) = ｛i, d, (, ｝ FIRST( A ) =｛i, d, ( ｝ FOLLOW( E ) =｛ , # ｝ FOLLOW( E＇) =｛ , # ｝ FOLLOW( A ) =｛i, d, (, ), # ｝ (3) 改写后文法的预测分析表：
《编译原理》 课后练习参考答案
第 04 章 自顶向下的语法分析
课后练习参考答案 第 04 章 自顶向下的语法分析
1. 已知文法 G： S →（L | a L → S , L |） （1）构造文法 G 的预测分析表。 （2）若输入串为“ （ａ， ） ” ，请给出语法分析过程。 【解】 （1）求各非终结符的 FISRT 集和 FOLLOW 集： FIRST(S) = { (, a } FIRST(L) = { ) } FIRST(S) = { (, ), a } FOLLOW(S) = { ’,’, # } FOLLOW(L) = FOLLOW(S) ={ ’,’, # } 预测分析表： S L ( S→ ( L L→ S , L a S→ a L→ S , L , } L → ) #
共 4 页，第 2 页
《编译原理》 课后练习参考答案
第 04 章 自顶向下的语法分析
对(((a,a),∧,(a)),a)的最左推导为： S→(T) →(T,S) →(S,S) →((T),S) →((T,S),S) →((T,S,S),S) →((S,S,S),S) →(((T),S,S),S) →(((T,S),S,S),S) →(((S,S),S,S),S) →(((a,S),S,S),S) →(((a,a),S,S),S) →(((a,a),∧,S),S) →(((a,a),∧,(T)),S) →(((a,a),∧,(S)),S) →(((a,a),∧,(a)),S) →(((a,a),∧,(a)),a) (2) 改写文法为： 0) S→a 1) S→∧ 2) S→( T ) 3) T→S N 4) N→, S N 5) N→ε 非终结符 S T N FIRST 集 {a,∧,(} {a,∧,(} {,,ε} FOLLOW 集 { #, , , ) } {)} {, S N）={，} FIRST（→ε）={ε} FOLLOW（N）={)} 由于 SELECT(N →, S N)∩SELECT(N →ε) ={，}∩ { )}= 所以文法是 LL(1)的。
共 4 页，第 3 页
《编译原理》 课后练习参考答案
第 04 章 自顶向下的语法分析
预测分析表（Predicting Analysis Table） S T N a → →S N ∧ → →S N ( →(T →S N ) , #
→ε
→, S N
也可由预测分析表中无多重入口判定文法是 LL(1)的。
(4) 对输入串（a,a）#的分析过程为： 栈(STACK) #S 当前输入符 （CUR_CHAR） 剩余输入符 （INOUT_STRING） 所用产生式 （OPERATION）
i E E＇ A E→iAE＇ E＇→AE＇ A→i E＇→AE＇ A→d E＇→AE＇ A→ (E) E → E→ d ( ) #
预测分析表中无多重入口，因此该文法是 LL(1) 文法.
3. 对文法 G[S] ：S→a|∧|(T) T→T,S|S (1) 给出(a,(a,a))和(((a,a),∧,(a)),a)的最左推导。 (2) 对文法 G，进行改写，然后对每个非终结符写出不带回溯的递归子程序。 (3) 经改写后的文法是否是 LL(1)的?给出它的预测分析表。 (4) 给出输入串(a,a)#的分析过程，并说明该串是否为 G 的句子。 【解】 (1) 对(a,(a,a)的最左推导为： S→(T) →(T,S) →(S,S) →(a,S) →(a,(T)) →(a,(T,S)) →(a,(S,S)) →(a,(a,S)) →(a,(a,a))
( ( a a a , , a a ) ) #
a,a)# a,a)# ,a)# ,a)# ,a)# a)# a)# )# )# # #
S→(T)
#)T( #)T #)NS #)Na #)N #)NS, #)NS #)Na #)N #) #
T→SN S→a
N→,SN S→a N→ε
可见输入串（a,a）#是文法的句子。
共 4 页，第 4 页