第一章  高级语言与编译程序概述
典型例题:
单项选择题
1.1.1．将编译程序分成若干个“遍”是为了___。
a.提高程序的执行效率
b.使程序的结构更加清晰
c.利用有限的机器内存并提高机器的执行效率
d.利用有限的机器内存但降低了机器的执行效率
1.1.2．构造编译程序应掌握____。（陕西省2000年自考题）
a.源程序        b.目标语言
c.编译方法      d.以上三项都是
1.1.3．变量应当＿。
a.持有左值                b.持有右值
c.既持有左值又持有右值  d.既不持有左值也不持有右值
1.1.4．编译程序绝大多数时间花在____上。（陕西省1998年自考题）
    a.出错处理      b.词法分析
    c.目标代码生成  d.管理表格
1.1.5．____不可能是目标代码。  ( 陕西省1997年自考题)
    a.汇编指令代码      b.可重定位指令代码
    c.绝对指令代码      d.中间代码
1.1.6．数组A[1…20,1…10]的首地址偏移量为0，按列存储，每个元素占一个字节，存储器
按字节编址，则A[i,ｊ］的偏移地址为____。
    a.(i-1)X10+（j-1）  b.(i-1)X20+(j-1)
    c. (i-1)＋(j-1)X10  d.(i-1)+(j-1)X20
1.1.7.使用____可以定义一个程序的意义。
a.语义规则    b.词法规则
c.产生规则    d.左结合规则
1.1.8．表达式X:=5中，变量x____。
a.只有左值            b.只有右值
c.既有左值又有右值    d.没有左值也没有右值
1.1.9．词法分析器的输入是__。
    a.单词符号    b.源程序
    c.语法单位    d.目标程序
1.1.10．中间代码生成时所遵循的是＿。
a.语法规则    b.词法规则
c.语义规则    d.等价变换规则
1.1.11．编译程序是对__。
a.汇编程序的翻译    b.高级语言程序的解释执行
c.机器语言的执行    d.高级语言的翻译
1.1.12．词法分析应遵循＿。      （陕西省2000年自考题）
a.语义规则  b.语法规则
c.构词规则  d.等价变换规则
 
多项选择题：
1.2.1 编译程序各阶段的工作都涉及到___。  （陕西省1999年自考题）
a.语法分析    b.表格管理  c.出错处理
d.语义分析    e.词法分析
1.2.2下列各项中，____与数组元素的地址有关。  （陕西省1999年自考题）
a.数组第一个元素的存储地址    b.数组的存储方式
c.数组的维数      d.内存的编址方式    e.编译程序
1.2.3 编译程序工作时,通常有__阶段。  （陕西省1998年自考题）
a.词法分析    b.语法分析  c.中间代码生成
d.语义检查    e.目标代码生成
1.2.4 过程调用的参数传递方式有__。
a传名  b.传值  c.传参数   
d.传地址 e.传结果
1.2.5 编译过程中所遵循的规则有____。
a.等价变换规则b.短语规则c.构词规则
d. 语义规则    e.语法规则
 
填空题：
1.3.1  解释程序和编译程序的区别在于＿。
1.3.2  编译过程通常可分为5个阶段，分别是＿、语法分析、＿、代码优化和目
标代码生成。（陕西省1999年自考题）
1.3.3  编译程序工作过程中，第一阶段输入是＿，最后阶段的输出为一程序。
                                                        （陕西省1997年自考题）
1.3.4  静态数组元素地址的计算公式由两部分确定，一部分是＿，它在＿时确定；
另一部分是＿，它在＿时确定。
1.3.5  把语法范畴翻译成中间代码所依据的是语言的＿。（陕西省2000年自考题）
1.3.6  目标代码可以是＿指令代码或＿指令代码或绝对机器指令代码。
                                                      （陕西省2000年自考题）
1.3.7  编译程序是指能将____程序翻译成____程序的程序。
1.3.8  数组元素的地址由___和___组成，其中＿中的a和c在翻译数组说明语句时填入到数组的＿中。
1.3.9  过程调用时，参数传递的方式有______、______、_____。
1.3.10  词法分析所遵循的是语言的______，而中间代码生成所遵循的是语言的_____。
                                                      （陕西省1997年自考题）
1.3.11  数组元素的地址计算与数组的_____数及____方式有关，也与数组的类型及机器对存
储器的编址方式有关。                                  （陕西省2000年自考题）
 
判断题：
1.4.1．赋值号左边的变量只持有左值，不持有右值。                    （ ）
1.4.2．二维数组a[3…15,5…20]按行存放，并且每个元素占用一个存储单元，则数组元素a[i ,j]的地址为base-85+i X 16+j (base是数组a存放的起始地址）。          （ ）
1.4.3．变量的名字用标识符来表示，同时名字代表一定的存储单元，有属性、值、作用域等特性。                          （陕西省1997年自考题）          （ ）
1.4.4．指示器变量的右值只持有右值，没有左值。（陕西省2000年自考题） （ ）
1.4.5．般而言，中间代码是一种独立于具体硬件的记号系统。            （ ）
 
综合题   
1.5.1  计算机执行用高级语言编写的程序有哪些途径？它们之间的主要区别是什么？
 
1.5.2  何谓“标识符”，何谓“名字”，两者的区别是什么？
 
1.5.3  简述在过程调用中，形参和实参间常见的各种信息传递方式（即形实结合方式）的含义。
 
1.5.4  画出编译程序的总体结构图，简述各部分的主要功能。
 
1.5.5  对于下面的程序：
PROCEDURE P(x,y,z)；
  BEGIN｛P｝
    y：=y+l；
    Z：=Z+X
  END；｛P｝
BEGIN { main}
A：=2；
B：=3；
P（A+B,A,A）；
Print A
END．{ main}
    若参数传递的办法分别为（1)传名，(2）传地址，(3）传结果，(4)传值；试问，程序
执行时所输出的A值分别是什么？
 
 
1.5.6  对于下面的程序：
                PROGRAM  main；
                a:integer；
                PROCEDURE test(x：:integer)；
                    temp:integer；
                BEGIN {test}
                          x：=a+l；
                      Temp：=a+2
                            x：=temp
                      END；{ test}
                          BEGIN
                          a:=2；
                          test(a)；
                print(a)
                      END．
分别给出参数传递为传地址、传结果、传值和传名时a的输出结果。
 
 
1.5.7  三维数组a[2:5,-2:2,5:7]首址为100,每个数组元素占4个存储单元，求数组元素a[3,1,6]
的地址。
 
 
1.5.8  什么叫自展？什么叫交叉编译？
 
 
1.5.9  试分析编译程序是否分遍应考虑的因素及多遍扫描编译程序的优缺点。
 
 
                                       
1.5.10  请画出编译程序的总框。如果你是一个编译程序的总设计师，应当考虑哪些问题？（国防科大2000年研究生试题）
 
 
                                     
1.5.11  对于下面说明语句所定义的数组A
                        array  A[-2:3,-5:5]
假定数组按行存放，存储器按字节编址，每四个字节为一机器字，令A的首地址为1000，问A[i+3,j+2]的首地址是什么？（写出步骤）（同济大学1998年研究生试题）
 
 
1.5.12  数组var a：array[1..5,-3..6] of integer；按列存放，其首址100,每个整数占4个字节，内存按字节编址，则数组元素a[4,3]的地址是什么？  （上海交大1997年研究生试题）
 
 
 
 
1.5.13  对于下面的程序段
…
          procedure  P(x,y,z)
            begin
                y：=y*2；;
                z：=x+z；
              end；
        begin
                  a：=5；
                  b：=2；
                p(a*b,a,a)；
                print(a)
            end．
    若参数传递的方法分别为（1)传值、(2)传地址、(3)传名，试问程序执行所输出的结
果分别是什么？
 
 
1.5.14  有一段程序为：
PROGRAM sample;
      x：integer；
PROCEDURE sun(m：integer)；
      BEGIN｛sun｝
      M：=11； x：=m+
      END；｛sun｝
BEGIN
      X：=100；
      sun（x）；
      write（x）
END；
    请用（1）传地址；（2）传值；（3）传结果；(4)传名的参数传递方式，给出程序的运行
结果。
 
 
 
 
1.5.15有一程序如下：
                        PROGRAM ex；
                          a：integer；
                        PROCEDURE PP(x：integer)；
                          BEGIN｛PP｝
                            a：=5；x：=a+1
                          END；｛PP｝
                        BEGIN
                          a：=2；
                        PP（a）；
                        write（a）
                        END ．
    用（1)传地址；(2)传值；（3)传结果；(4)传名等4种参数传递方式，；试写出程序的
运行结果。
5
※<习题二>
第二章  词法分析
典型例题:
单项选择题
1.1.1．词法分析所依据的是____。
a.语义规则  b.构词规则
c.语法规则  d.等价变换规则
1.1.2．词法分析器的输出结果是____。
a.单词的种别编码          b.单词在符号表中的位置
c.单词的种别编码和自身值  d.单词自身值
1.1.3．正规式MI和M2等价是指____。
a. MI和M2的状态数相等        b.Ml和M2的有向弧条数相等。
C.M1和M2所识别的语言集相等    d. Ml和M2状态数和有向弧条数相等
1.1.4．状态转换图（见图2.5），接收的字集为：
 
 
图2.5
a.以0开头的二进制数组成的集合
b.以0结尾的二进制数组成的集合
c.含奇数个0的二进制数组成的集合
d.含偶数个0的二进制数组成的集合
1.1.5．词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确，因此___。
a.词法分析器应作为独立的一遍
b.词法分析器作为子程序较好
c.词法分析器分解为多个过程，由语法分析器选择使用
d.词法分析器并不作为一个独立的阶段
1.1.6．词法分析器的输入是—。
        a.单词符号串    b.源程序
        c.语法单位      d.目标程序
1.1.7.如果L(M)=L(M'），则M与M'__。（陕西省1999年自考题）
    a. 等价                  b．M与M'都是二义的
    c. M与M'都是无二义的    d. 他们的状态数相等
1.1.8．图2.56所示的状态转换图接受的字集所对应的正规式为＿。（陕西省1997年自考题）
                                                   
a. a*b*(aa|bb)a*b*    b. (a|b)*(aa|bb)(a|b)
c. (a*|b*)(aa|bb)(a*|b*)    d. (a*|b*)aa(a*|b*)|(a*|b*)bb(a*|b*)
图2.56  状态转换图
 
多项选择题：
1.2.1在词法分析中，能识别出＿。                        （陕西省1998年自考题）
        a.基本字    b.四元式      c.运算符
        d.逆波兰式      e..常数
1.2.2令∑={a,b}，则∑上所有以b开头，后跟若干个ab的字的全体对应的正规式为＿。
      a．b(ab)*    b.b(ab)      c.(ba)* b
      d.(ba)+b    e. b(alb)*
1.2.3设∑={0,1}，则∑上字的全体可用正规式_____表示。
      a.(1|0)*      b.(1*|0*)*      c.(1|0)+
            d.(1*0*)*        e.(10)*
 
填空题：
1.3.1  确定有限自动机DFA是_______的一个特例。
1.3.2  若二个正规式所表示的______相同，则认为二者是等价的。（陕西省1997年自考题）
1.3.3  一个字集是正规的，当且仅当它可由______所______（陕西省1997年自考题）
 
判断题：
1.4.1．一个有限状态自动机中，有且仅有一个唯一的终态。                （  ）
1.4.2．设r和s分别是正规式，则有L(r|s)=L(r)|L(s)                    （  ）
1.4.3．自动机M和M'的状态数不同，则二者必不等价。                    （  ）
1.4.4．确定的自动机以及不确定的自动机都能正确地识别正规集。          （  ）
1.4.5．对任意一个右线性文法G，都存在一个NFA M，满足L(G)=L(M)。      （  ）
1.4.6  对任意一个右线性文法G,都存在一个DFA M,满足L(G}=L(M) 。        （  ）
1.4.7  对任何正则表达式e,都存在一个NFA M,满足L(G)=L(e) 。          （  ）
1.4.8  对任何正则表达式e,都存在一个DFA M,满足L(G)=L(e)。            （  ）
1.4.9  两个正规集相等的必要条件是他们对应的正规式等价。（）
1.4.10  词法分析作为单独的一遍来处理较好。（）
1.4.11  一张转换图只包含有限个状态，其中有一个被认为是初态，最多只有一个终态。（）
 
综合题
1.5.1  什么是扫描器？扫描器的功能是什么？
 
1.5.2  给出字母表∑上的正规式及其所描述的正规集的递归定义。
 
1.5.3  正规文法、正规式、确定有限自动机和非确定有限自动机在接收语言能力上是否相互等价？
 
1.5.4  已知Pascal语言的实数表示规则如下：
      （1)实数十进制表示
      (a)实型数的小数点前后必须出现数字：
      (b）必须出现小数点。
      （2）实数科学表示（指数形式）
      (a)字母e表示以十为底的指数；
      (b）字母e前必须出现实数或者整数；
      （c）字母e后必须出现整数，这个整数表示实型数的指数部分。
试画出该实数对应的状态转换图。
 
1.5.5  设M= <{x,y}，{a,b) ,f,x, {y})为一非确定的有限自动机，其中f定义如下：
f(x,a)=｛x,y｝  f｛a,b｝=｛Y)
                      f(Y,a)=φ      f｛y,b｝＝｛x,y｝
试构造相应的确定有限自动机M`。
 
1.5.6  (1）对给定正规式b*(d|ad) (b|ab)＋，构造其NFA  M；    （陕西省1997年自考题）
（2) 对给定正规式(a|b)*a (a|b)，构造其DFA  M。  （中科院计算所1997年研究生试题）
 
1.5.7  构造一个DFA,它接收∑=｛a,b｝上的所有满足下述条件的字符串，即该字符串中的每个a都有至少一个b直接跟在其右边。
 
1.5.8  有穷状态自动机M接受字母表∑＝{0，1｝上所有满足下述条件的串：串中至少包含两个连
续的0或两个连续的1。
    （1)请给出与M等价的正规（则）式。
    （2）将M最小化。
    （3）构造与M等价的正规文法。
 
1.5.9  构造正规表达式((a|b)*|bb)*的ＤＦＡ（要求写出步骤）。
 
1.5.10  设有L(G)={a2n+1b2ma2p+1|n≥0,p≥0,m≥1}
  （1)给出描述该语言的正规表达式。
    (2)构造识别该语言的确定的有穷自动机（可直接用状态图形式给出）。
 
1.5.11  请写出在∑＝(a,b)上，不是a开头的，但以aa结尾的字符串集合的正规表达式，并构造与之等价状态最少的DFA。
 
 
1.5.12  有语言L={w|w∈(0,1）＋，并且w中至少有两个1，又在任何两个1之间有偶数个0，试构造接受该语言的确定有限状态自动机（DFA）。
 
1.5.13  已知正规式(1)((a|b)*|aa)*b和正规式(2)(a|b)*b。
(1)试用有限自动机的等价性证明正规式(1)和(2)是等价的。
(2）给出相应的正规文法。
 
1.5.14  某操作系统下合法的文件名为sion,其中第一部分（device:）和第三部分（.extension)可缺省，若device, name和extension都是字母串，长度不限，但至少为1，画出识别这种文件名的确定有限自动机。
 
1.5.15  Pascal语言无符号数的正规定义如下：
              Num→digit+(.digit+)?(E(+|-)?digit+)?
其中digit表示数字，用状态转换图表示接受无符号数的确定有限自动机。
 
1.5.16  在C语言中无符号整数可用十进制（非0打头）、八进制（0打头）和十六进(0X打头）表示，试写出其相应的文法和识别无符号数的DFA(假定位数不限)。
 
1.5.17  下列程序段若以B表示循环体，A表示初始化，I表示增量，T表示测试。
            I:=1；
while I<=n do
begin
sun:=sun+a[I];
              I:=I+l
              End
请用正规表达式表示这个程序段可能的执行序列。
 
1.5.18  在操作系统的进程管理中，进程的状态转换如图2.50所示。假设现有两个进程Pi和CPU每次只能运行一个进程。当P1、P2都处于就绪状态时为初态，当P1、P2都处于睡眠状态时为终态。请用一个有限自动机来描述这个进程管理系统。
 
图2.50  进程状态转换图
 
 
1.5.19  有一台自动售货机，接收1分和2分硬币，出售3分钱一块的硬糖。顾客每次向机器中
投放≥3分的硬币，便可得到一块糖（注意：只给一块并且不钱）。
    (1)写出售货机售糖的正规表达式。
    (2)构造识别上述正规式的最简DFA。
 
1.5.20  证明：一不含无用状态的有限自动机M的接收集L(M)是无限集，当且仅当M相应的状态转换图中含有回路。
 
1.5.21  假定A和B都是正规集，请用正规集与有限自动机的等价性说明A∪B也是正规的。
 
1.5.22  下面的正规式等价吗？为什么？
(1)(a|b)*  (2) (a*|b*)*  (3)((ε|a)b*)*
 
1.5.23  （电子科大1996年研究生试题）
构造识别下列单词符号的状态转换图：
                begin end标识符正整数＋－***，．∷＝
 
1.5.24  （清华大学1998年研究生试题）
请将图2.57所示的有穷自动机M1最小化。
 
图2.57 有穷自动机M1
 
1.5.25  （清华大学1998年研究生试题）             
将有穷自动机M2确定化
                  M2=({U,V,W,X}，10,1｝,f,{U}，{W}）
其中：f(U,0）＝φ    f(U,1）＝｛V,X}
      f(V,0)={V}      f(V,l）＝tvlwl
      f(W,0)={X｝    f(W,1)＝{W}
      f(X,0)={X}      f(X,1）＝{X}
 
 
1.5.26  （清华大学1998年研究生试题）
将图2.58所示的DFA最小化。
 
图2.58 DFA
 
 
1.5.27  （中科院计算所1997年研究生试题）
为正规式(a|b) *a(a|b)构造一个确定的有限自动机。
 
1.5.28  （南开大学1998年研究生试题）
写出正规式(alb) *(aa|bb)(a|b)*的DFA。
 
1.5.29  （复旦大学1999年研究生试题）
将图2.59所示的非确定有限自动机(NFA)变换成等价的确定有限自动机(DFA)。
 
图2.59  NFA
其中，X为初态，Y为终态。
 
1.5.30 （上海交大1997年研究生试题）
请构造与正规式R=(a*|b*)b(ba)*等价且状态最少的DFA。
 
1.5.31  （国防科大1999年研究生试题）
构造一个确定的有限自动机DFA,它接受∑＝{0,1}上的所有不带前导0的二进制区数。
 
1.5.32  （国防科大2000年研究生试题）
已知DFA M如图2.60所示。
图2.60 DFA  M
请给出M所识别的字的全体L(M)。
 
1.5.33  （华中理工2001年研究生试题）
  构造一个确定的有穷自动机DFA M,它识别∑={a,b}上所有满足如下条件的字符串：字
符串由a, b组成，且其中b的个数为3k (k≥0)。
 
1.5.34  （华中理工2001年研究生试题）
正规式(ab）*a与正规式a(ba) * 是否等价？请说明理由。
 
1.5.35  DFA与NFA有何区别
5
※<习题三>
第三章  语法分析
典型例题:
单项选择题
    3.1.1. 文法G: S-xSxly所识别的语言是_____（陕西省1997年自考题）
      a. xyx  b. (xyx)*  c. xnyxn(n≥0)  d. x*yx*
    3.1.2. 文法G描述的语言L(G)是指_____。
      a.  L(G)=｛α|S=>α，α ∈VT*｝b. L(G)={ α|SA=>α,α ∈VT*｝
      c．L(G)={ α|S=>α，α∈(VT∪VN)*｝d. L(G)=｛α|S=>α,α∈(VT∪VN)*｝
    3.1.3. 有限状态自动机能识别＿。
      a.上下文无关文法          b.上下文有关文法
      c.正规文法                d.短语文法
    3.1.4. 设G为算符优先文法，G的任意终结符对a, b有以下关系成立____。
      a.若f(a)>g(b)，则a>b      b.若f(a)<g(b)，则a<b
      c.a~b都不一定成立      d. a~b一定成立
    3.1.5．茹果文法G是无二义的，则它的任何句子α_＿。（西电1999年研究生试题）
      a.最左推导和最右推导对应的语法树必定相同
      b.最左推导和最右推导对应的语法树可能不同
      c.最左推导和最右推导必定相同
      d.可能存在两个不同的最左推导，但它们对应的语法树相同
  3.1. 6.由文法的开始符经。步或多步推导产生的文法符号序列是____。
                                                            （陕西省2000年自考题）
      a．短语  b.句柄  c.句型  d.句子
3.1.7．文法G：E-E+TIT
          T-T*P|P
          P-(E)|I
则句型P+T+i的句柄和最左素短语分别为__＿。
  a. P+T和i  b. P和P+T c. i和P+T+i  d. P和P
3.1.8．设文法为：S--SA|A
                  A→a|b
则对句子aba，下面____是规范推导．
          a. S=>SA=>SAA=>AAA=>aAA=>abA=>aba
          b. S=>SA=>SAA=>AAA=>AAa=>Aba=>aba
          c. S=>SA=>SAA=>SAa=>Sba=>Aba=>aba
          d. S=>SA=>Sa=>Sba=>Aba=>aba
3.1.9.文法G:  S→b|∧|(T)
          T-T,SIS
则FIRSTVT(T)=____。
        a.｛b，∧，（｝  b.｛b，∧，）｝  c.｛b,∧，（，,｝  d.{b, ∧，），，｝
 
3.1.10．产生正规语言的文法为____＿。
      a. 0型  b. 1型  c. 2型  d. 3型
    3.1.11．任何算符优先文法—优先函数。
        a.有一个  b.没有  c.有若干个  d.可能有若干个
    3.1.12.采用自上而下分析，必须____＿。
        a.消除左递归      b.消除右递归
        c.消除回溯．      d.提取公共左因子
    3.1.13．设a, b, c是文法的终结符，且满足优先关系a=b和b=c，则_____＿。
        a.必有a=ｂ        b．必有c=a
        c.必有b=a        d. a~c都不一定成立
    3.1.14.在规范归约中，用___＿来刻画可归约串。（陕西省1999年自考题）
        a.直接短语  b.句柄  c.最左素短语  d.素短语
    3.1.15.有文法Ｇ：E→E*T|T
                T→T+i|i
句子1+2*8+6按该文法G归约，其值为___＿。
          a.23    b.42    c.30    d.17
    3.1.16.规范归约是指________。（陕西省９８年自考题）
        a.最左推导的逆过程            b.最右推导的逆过程
        c.规范推导                  d.最左归约的逆过程
  3.1.17.一文法G:S→S+T|T．（陕西省1998年自考题）
              T→T*P|P
              P→(S)|i
则句型P+T+i的短语有___＿。
        a. i,P+T    b. P,P+T,i,P+T+i    c. P+T+i    d. P,　P+T,i
 
多项选择题：
3.2.1.下面哪些说法是错误的___＿。（陕西省1998年自考题）
        a.　有向图是一个状态转换图    b.状态转换图是一个有向图
        c．　状态转换图可以用DFA表示  d. DFA可以用状态转换图表示
        e.有向图是一个DFA
    3.2.2.对无二义性文法来说，一棵语法树往往代表了___＿。
      a.多种推导过程  b.多种最左推导过程  c.一种最左推导过程
        d.仅一种推导过程  e.一种最右推导过程
    3.2.3．如果文法G存在一个句子，满足下列条件___之一时，则称该文法是二义文法。
        a.该句子的最左推导与最右推导相同
        b、该句子有两个不同的最左推导
        c.该句子有两个不同的最右推导
        d,该句子有两棵不同的语法树
        e.该句子的语法树只有一个
    3.2.4.语法分析时通过___＿操作使用符号栈。（陕西省2000年自考题）
        a. 移进  b. 归约  c. 比较  d. 接受  e. 出错处理
    3.2.5.算符优先文法与算符优先函数的关系描述中，下列__＿正确。（陕西省1997年自考题）
        a、一个算符优先文法可能不存在算符优先函数与之对应
        b. 一个算符优先文法可能存在多对算符优先函数与之对应
        c.一个算符优先文法一定存在多对算符优先函数与之对应
        d.一个算符优先文法一定存在算符优先函数与之对应
        e.一个算符优先文法一定存在有限对算符优先函数与之对应
    3.2.6.有一文法G: S--AB                                （陕西省1998年自考题）
                A--aAb|ε
                B一cBd|ε
它不产生下面__＿集合。
      a.  {anbmcndm|n,m≥0} b. {anb"cmdm|n,m>0｝
      c. {anbmcmdn|n,m≥0}  d. {anbncmdm|n,m≥0}
      e. {anbncndn|n≥0}
    3.2.7．文法的无二义性是指_________。
        a.文法中不存在句子有两个不同的最左推导
        b.文法中不存在句子有两个不同的最右推导
        c.文法中不存在句子有不同的推导
        d.文法中不存在句子有两裸不同的语法树
        e.文法中不存在句子有不同的最左和最右推导
    3.2.8. 文法G：S→aAcB|Bd
              A→AaB|c
              B→bScA|b
则句型aAcbBdcc的短语是_______。
          a. Bd    b. c    c. bBdcc    d. aAcbBdcc    e. cbBd
    3.2.9.在自下而上的语法分析中，应从_________开始分析。
        a.句型    b.句子    c.以单词为单位的程序
        d.文法的开始符      e.句柄
    3.2.10.对正规文法描述的语言，以下_____＿有能力描述它。
        a. 0型文法    b. 1型文法    c.上下文无关文法
        d.右线性文法    e.左线性文法
 
填空题：
 
    3.3.1．规范归约中的可归约串是指______;算符优先分析中的可归约串是指______＿。
    3.3.2.文法中的终结符和非终结符的交集是______。词法分析器交给语法分析器的文法符号一定是______，它一定只出现在产生式的_____＿部。
    3.3.3.在自上而下的语法分析中，应先消除文法的_______递归，再消除文法的_____递归。
    3.3.4.规范归约是指在移进过程中，当发现栈顶呈现_____时，就用相应产生式的_____符号进行替换。
    3.3.5．当文法非终结符的所有_____两两___＿时，该文法对应的句子分析不含回溯。
    3.3.6.最左推导是指每次都对句型中的____＿非终结符进行扩展。（陕西省1998年自考题）
    3.3.7.在语法分析中，最常见的两种方法一定是_____分析法，另一是______分析法。                                              （陕西省1998年自考题）
    3.3.8.______语法分析的关键问题是精确定义可归约串的概念。（陕西省2000年自考题）
    3.3.9. Chomsky定义的4种形式语言文法为：
        ①______文法，又称______文法；②_____文法，又称_____文法；
        ③______文法，又称______文法；④______文法，又称_____＿文法。
                                      （中国科技大学1999年研究生试题）
    3.3.10. LL(K)文法中，第一个L表示_____＿，第二个L表示_____＿，K表示_____，通常情况下K_____。（西安电子科大2000年研究生试题）
3.3.11．采用_______＿语法分析时，必须消除文法的左递归。
    3.3.12．_____树代表推导过程，______＿树代表归约过程。
    3.3.13.自下而上分析法采用____＿、归约、错误处理、_____＿等四种操作。
                                                    （陕西省1999年自考题）
    3.3.14．设αβδ是文法G的一个句型，A是非终结符，则β是句型αβδ相对于A的短语，若______＿；β是句型αβδ相对于A的直接短语，若_____＿；β是句型αβδ的句柄，若_______。（西安电子科大2000年研究生题）
    3.3.15．Chomsky把文法分为______＿种类型，编译器构造中采用______和_____＿文法，它们分别产生_____和_____语言，并分别用______和______自动机识别所产生的语言。                                          （西安电子科大2000年研究生试题）
判断题：
3.4.1语法分析之所以采用上下文无关文法是因为它的描述能力最强。        （　）
3.4.2      欲构造行之有效的自上而下分析器，则必须消除左递归。    （  ）
3.4.3文法(  有图片    　)描述的语言是（a|bc）*              (    )
3.4.4 在自下而上的语法分析中，语法树与分析树一定相同。（  ）
3.4.5 二义文法不是上下文无关文法。（陕西省1999年自考题）（  ）
3.4.6 每一个算符优先文法，必定能到一组优先函数与之对应。（陕西省2000年自考题）          （  ）
3.4.7 语法分析时必须先消除文法中的左递归。        　（　）
3.4.8 规范归约和规范推导是互逆的两个过程。        　（　）
3.4.9 一个文法所有句型的集合形成该文法所能接受的语言。  　（　）
3.4.10  LL(1)文法一定不含左递归和二义性。            （　）
 
综合题
3.5.1  简答题  1．句柄  2.素短语  3．语法树  4.归约  5.推导
 
3.5.2给出上下文无关文法的定义。
 
3.5.3 Chomsky将文法分成四类。指明这四类文法与自动机的对应关系。指出右线性文法、左线性文法、正规文法之间的主要区别。
 
3.5.4 文法G是LL(1)文法的充分必要条件是什么？
 
 
3.5.5 文法G[S］：
              S→aSPQ|abQ
                QP→PQ
                    bP→bb
                bQ→be
                cQ→cc
    （1)它是Chomsky哪一型文法？
      （2）它生成的语言是什么？
 
 
3.5.6 指出下述文法的所有类型，并给出所描述的语言。
（1）S→Be （2）A→ε|aB（3）TS→abcA
      B→eC|Af  　B→Ab|a    S→Aabc
      A→Ae|e          A→ε
      C→Cf          　Aa→Sa
D→fDA          　cA→cS
 
3.5.7 按指定类型，给出语言的文法。
  （1）L=｛aidj>i≥l}的上下文无关文法。
    (2)字母表∑={a,b｝上的同时只有奇数个a和奇数个b的所有串的集合的正规文法。
    (3）由相同个数a和b组成句子的无二义文法。
 
3.5.8 下面的二义文法描述命题演算公式，为它写一个等价的非二义文法。
                        S→SandS|S or S|not S|p|q|(S)
 
3.5.9 有文法G：S→aAcB|Bd
              A→AaB|c
              B→bScA|b
    （1)试求句型aAaBcbbdcc和aAcbBdcc的句柄；
    (2)写出句子acabcbbdcc的最左推导过程。
 
3.5.10　对文法G：E→E+T|T
            T→T*P|P
            P→i
    （1)构造该文法的优先关系表（不考虑语句括号＃），并指出此文法是否为算符优先文法；
    (2）构造文法G的优先函数
 
3.5.11 在上一题中，如果将文法改为E→E+E|E*E|i,在不改动文法的情况下是否同样能构造出优先关系表？此外，针对例3.14中的文法与本例中的文法，对算符优先分析快于规范归约进行说明。
 
3.5.12  对于文法G[S]：
                  S→(L)|aS|a
                  L→L,S|S
    （1)画出句型（s，（a））的语法树。
    (2)写出上述句型的所有短语、直接短语、句柄和素短语。
 
3.5.13  构造算符文法G[H]的算符优先关系（含＃）。
                      G[H]：H→H;M|M
                            M→d|aHb
 
3.5.14  设有文法G[S]为：
                S→a|b|(A)
                A→SdA|S
（1)          完成下列算符优先关系表，见表3.6.并判断G[S]是否为算符优先文法。
(2）给出句型（SdSdS)的短语、简单短语、句柄、素短语和最左素短语。
（3)给出输入串(adb)#的分析过程。
 
 
3.5.15 下面映射if语句的文法G[S]是算符优先文法吗？若是，则构造其优先关系矩阵。若不是，请按照多数程序设计语言（如Pascal)的习惯，给出一个相应的算符优先文法。
                          G[S]：S→iBtS|iBtSeS|a
                                B→b
 
 
3.5.16  文法G[<stmt>]不是LL(l)的，请说明理由，并给出其等价的LL(1)文法。
                      G[<stmt>]:
                                  <stmt>→<label> <unlabelstmt>
                            <lable>→i:|ε
                            <unlablestmt>→i=e
 
3.5.17 已知文法G[A]为：
            A→aAB1|a
              B→Bb|d
（I）试给出与G[A]等价的LL(I）文法G’[A]。
（2)构造G’[A］的预测分析表。
（3）给出输入串aadl#分析过程。
 
3.5.18  将G[V]改造为LL（1）文法。
                  G[V]: V→N|N[E]
                  E→V|V+E
                  N→i
 
3.5.19  有文法G[S]: S-BA
                A--BS|d
                B～aA|bS|c
    (I）证明文法G是LL(I）文法。
    （2）构造LL（1）分析表。
      (3）写出句子adccd的分析过程。
 
      3.5.20  考虑文法G[T]：
                T→T*F|F
              F→F↑P|P
                P→(T)|i
（1)证明T*P↑(T*F)是该文法的一个句型，并指出其直接短语和句柄。
(2)构造文法G的优先关系表（要求写出步骤）。
 
3.5.21  给出算符优先文法的分析算法。
 
3.5.22  文法G的产生式集为：S→S+S|S*S|i|（s），对于输入串i+i*i；
    （1)给出一个推导；
    (2）画出一棵语法树；
    （3)文法G是否是二义性的，请证明你的结论。
 
3.5.23  已给文法G[E]：
                E→EOE|(E)|i
                0→+|*
试将其改造为可进行不带回溯的自顶向下分析的文法，并给出其相应的LL(1)分析表。
 
3.5.24  考虑文法G(S)：
                S→(T)|a+S|a
                T→T,S|S
    消除文法的左递归及提取公共左因子，然后，对每个非终结符，写出不带回溯的递归子程序。
 
 
3.5.25 有映射程序设计语言if-the-else语句的文法G[S]:                            S→iEtSeS|EtS|a
                                      E→b
其中，else遵从最近匹配原则。
    （1)试改造文法，并为之构造LL（1）分析表。
    (2）利用构造的分析表分析句子ibtibtaea,要求给出分析过程中每一步的分析栈和输入串的变化以及输出信息。
 
3.5.26 下述文法描述了C语言整数变量的声明语句：
                              D→TL
                    T→int|long|short
                    L→id|L,id
      （1)改造上述文法，使其接受相同的输入序列，但文法是右递归的。
      (2)分别用上述文法和改造文法，为输入序列int a,b,c构造分析树。
 
 
 
3.5.27  设有文法G[W]：
                      W→AO
                                                                                                                                                                                                      A→AO|W1|0
请改写文法，消除规则左递归和文法左递归。
 
3.5.28 文法G[P]及相应翻译方案为：
                            P→bQb {print:”1”｝
                            Q→cR {print:”2”｝
                            Q→a {print:”3”｝
                            R→Qad (print:”4”｝
    （1)该文法是不是算符优先文法，请构造算符优先关系表证实之。
    (2)输入串为bcccaadadadb时，该翻译方案的输出是什么。
 
3.5.29  设有文法G[S]：
                S→SAS|b
                A→bSb|b
试构造一个与其等价的算符文法。
 
3.5.30  在算符优先分析法中，为什么要在到最左素短语的尾时，才返回来确定其对应的头，能否按扫描顺序先到头后到对应的尾，为什么？
 
3.5.31  试证明在算符文法中，任何句型都不包含两个相邻的非终结符。
 
3.5.32假定文法包含产生式A→α，α∈V*（V是文法的词汇表，由终结符和非终结符组成的集合），证明：如果FIRST（α）∩FOLLOW（A）≠φ，则该文法不是LL（1)文法。
 
3.5.33  给出文法G1：
              S→aSb|P
              A→bPc|bQc
            B→Qa|a
    （1)它是Chomsky哪一型文法？
    （2）它生成的语言是什么？
    （3)它是不是算符优先文法？请构造算符优先关系表证实之。
    (4)请证实所有①左递归文法②有公共左因子的文法均不是LL（1)文法。
    (5)文法G1消除左递归、提取公共左因子后是不是LL (1）文法？请证实。
 
3.5.34  简答题
    （1)什么是文法的二义性？二义性问题的不可判定指的是什么？
    (2)在规范句型中，句柄以右的符号有什么特征？为什么？
 
3.5.35  写正规文法G,它产生的语言是L(G)={ anibncp|m,n,p≥0}
 
3.5.36  语言L是所有由偶数个0和偶数个1组成的句子的集合，给出定义L的正规文法。
 
3.5.37  已知文法G[S］：S→ABS|AB
                          AB→BA
                          A→0
                        B→1
该文法是几型的？该文法所产生的语言是什么？（用自然语言描述）写出与该文法等价的CFG文法。
 
3.5.8  写一个上下文无关文法G，使得L(G)={anbmcmdn|n≥0,m≥1｝。
 
3.5.39  写一个文法G，使其语言为L(G)={ anbm|n≥m≥1｝。
 
3.5.40 生成语言1={albmclanbn|1>=O,m>=1，n>=2｝的文法是什么？它是Chomsky那一型文法？
 
3.5.41文法G[P]：P→aPQR|abR
                RQ→QR
                bQ→bb
                    bR→be
                    cR→cc
它是Chomsky哪一型文法？请证aaabbbccc是G[P]的一个句子。
 
3.5.42文法G[S］：S→aSPQ|abQ
          QP→PQ
            bP→bb
          bQ→be
          cQ→cc
（1)它是Chomsky哪一型文法？
（2）它生成的语言是什么？
 
3.5.43  给定文法G[S]：S→(S)S|ε，给出句子（（）（））（）（）的规范推导，并指出每步推导所得句型的句柄，画出该句子的语法推导树，指出所有的短语和直接短语。
 
3.5.44  设文法G[S]：S→(A)|a
              A→A+S|S
（1）构造各非终结符的FIRSTVT和LASTVT集合。
（2）构造优先关系表。
 
3.5.45已知文法G[S]：S→dAB
              A→aA|a
                B→Bb|ε
（1)试问G[S]是否为正规文法，为什么？
(2）G[S]所产生的语言是什么？
（3) G[S]能否改写为等价的正规文法?
 
3.5.46 选择题
    有文法G[S]：S→aA|a|bC，A→aS|bB，B→aC|bA|b，C→aB|bS，则____＿为L(G)
中句子。
      a. aloob5oabloo    b. alooob5ooaba
      c. a500b60aab2a      d. a l00 b4oab10 aa
 
3.5.47  对文法G[S‘］：S‘→#S#
                    S→fstS
                    S→i=E
                E→E+T|T
              T→P↑T|P
                P→(E)|i
    （1）求各非终结符的FIRSTVT和LASTVT集合。
    (2）构造该文法的优先关系表。（请将终结符以＝＋、↑、（、i, f, t,）、＃的顺序构造优先关系表）
 
 
3.5.48  有文法R::=i|(T)，T::=T，R|R，完成表3.21所示的算符优先关系表（填写第一、第二行）。
 
 
3.5.49  文法G[M]是否LL(1)的，说明理由。
                      G[M]：M→TB
                            T→Ba|ε
                          B→Db|eT|ε
                            D→d|ε
3.5.50  将文法G[E]改写为等价的LL(I)文法，并给出相应的预测分析表。
                    G[E]：E→[T
                          T→F]|TE
                          F→i|Fi
3.5.51  已知文法G[S]: S→S*aP|aP|*aP
                P→+aP|+a
（1）将文法G[S]改写为LL(1）文法G‘［S］。
(2)写出文法G' [S]的预测分析表。
5
※<习题四>
第四章              语法分析器的自动构造
 
典型例题:
单项选择题
4.1.1.若a为终结符，则A→a·aβ为____＿项目。
        a.归约  b.移进  c.接受  d.待约
4.1.2.两个LR(1)项目集如果除去______后是相同的，则称这两个LR(1)项目同心。
        a.项目    b.活前缀    c.搜索符  d.前缀
4.1.3．同心集合并不会产生—冲突。
        a.二义  b.移进／移进  c.移进／归约  d.归约／归约
4.1.4．左结合意味着____＿。
        a.打断联系实行移进    b.打断联系实行归约
        c.建立联系实行移进    d.建立联系实行归约
4.1. 5.若项目集Ik含有A→a·，则在状态k时，仅当面临的输入符号a∈FOLLOW(A)
时，才采取“A→a·”动作的一定是_____。
      a. LALR文法    b. LR(0)文法    c. LR(1)文法    d. SLR(1)文法
4.1.6．就文法的描述能力来说，有____＿。
        a. SLR(1）cLR(0)  b. LR(1）cLR(0) 
        c. SLR(1）cLR(1）  d.无二义文法cLR(1）
4.1. 7.在LR(0)的ACTION子表中，如果某一行中存在标记为"ri”的栏，则___＿。
      a.该行必定填满ri      b.该行未填满ri
      c.其他行也有ri        d. goto子表中也有ri
4.1.8.一个____指明了在分析过程中的某时刻所能看到产生式多大一部分。
        a.活前缀    b.前缀    c.项目    d.项目集
4.1.9.若B为非终结符，则A→a·Bβ为____项目。
        a.接受  b.归约  c.移进  d.待约
4.1.10．同心集合并有可能产生新的＿冲突。
        a.归约  b.移进／移进  c.移进／归约  d.归约／归约
4.1.11．右结合意味着＿。
        a.打断联系实行归约  b.建立联系实行归约
        c.建立联系实行移进  d.打断联系实行移进
4.1.12.若项目集Ik含有A→a·，则在状态K时，无论面临什么输入符号都采取“A→α
归约”的动作一定是＿。
      a. LR(1）文法  b. LALR(1)文法  c. LR(0)文法  d. SLR(1）文法
4.1.13．就文法的描述能力来说，有＿。
        a.无二义文法cSLR(1）  b. LR(0) cLR(1)
        c.无二义文法cLR(0)  d. LR(1) cLR(0)
多项选择题：
4.2.1．一个LR分析器包括____。
        a.一个总控程序      b.一个项目集。    c.一个活前缀
        d.一张分析表        e.一个分析栈
    4.2.2 ．LR分析器核心部分是一张分析表，该表包括_____等子表。
        a. LL(1）分析    b.优先关系    c. GOTO
          d. LR    e. ACTION
    4.2.3．每一项ACTION[S,a]所规定的动作包括______。
a.移进  b.比较  c.接受  d.归约  e.报错
    4.2.4.对LR分析表的构造，有可能存在_____动作冲突。
        a.移进    b.归约    c.移进／归约  d.移进／移进e  .归约／归约
    4.2.5．就文法的描述能力来说，有____。
        a. SLR(1）c LR(1）    b. LR(0)        c SLR(1）c. LR(0) c LR(1）
      d. LR(1）c无二义文法      e. SLR(1）c无二义文法
    4.2.6．对LR分析器来说，存在＿___等分析表的构造方法。
        a. LALR  b. LR(0)    c. SLR(1)    d. SLR(0)    e. LR(1)
    4.2.7.自上而下的语法分析方法有＿__。
      a.算符优先分析法      b. LL(1)分析法      c. SLR(1)分析法
      d. LR(0)分析法        e. LALR(1)分析法
填空题：
4.3.1．对于一个文法，如果能够构造___，使得它的____均是唯一确定的，则称该文法
为LR文法。
4.3.2.字的前缀是指该字的＿___。
4.3.3．活前缀是指_____的一个前缀，这种前缀不含____＿之后的任何符号。
4.3.4.在LR分析过程中，只要＿的已扫描部分保持可归约成一个____，则扫描过的
部分正确。
4.3.5.将识别＿___的NFA确定化，使其成为以＿____为状态的DFA,这个DFA就是建
立的基础。
4.3.6. A→a·称为_____项目；对文法开始符S'，称S'→a·为＿__项目；若a为
终结符，则称A→a·aβ为__＿项目；若B为非终结符，则称A→a·Bβ为_____项目。
4.3.7. LR(0)分析法的名字中“L”表示，“R”表示，"0”表示______。
4.3.8．一个LR分析器包括两部分：________和_______.
4.3.9.两个LR(1)项目集如果除去＿_____后是相同的，则称这两个LR(1)项目集_____。
4.3.10.构成识别一个文法___＿的DFA的项目集全体，称为这个文法的LR(0) _____.
4..3.11.一个活前缀γ的＿___，就是从识别文法活前缀DFA的初态出发，经读出γ后所到达的那个
4.3.12．左结合意味着打断联系实行___＿，右结合意味着打断联系实行____＿。
4.3.13.同心集合并不会产生—冲突，但可能产生___＿冲突。
源程序能直接执行吗
 
判断题：
4.4.1. LR分析法在自左至右扫描输入串时就能发现错误，但不能准确地指出出错地点。 （）
4.4.2.构造LR分析器的任务就是产生LR分析表。                                  （）
4.4.3 .LR文法肯定是无二义的，一个无二义文法决不会是LR文法。                  （）
4.4.4.在任何时候，分析栈的活前缀Xm的有效项目集就是栈顶状态Sm所在的那个
项目集。                                                                      （）
4.4.5．同心集的合并有可能产生新的“移进”／“归约”冲突。                    （）
4.4.6.由于LR(0)分析表构造简单，所以它的描述能力强、适用面宽；LR(1)分析表因构造复杂而描述能力弱、适用面窄。                                                  （）
4.4.7．所有LR分析器的总控程序都是一样的，只是分析表各有不同。              （）
4.4.8. LR分析技术无法适用二义文法。                                          （）
4.4.9.项目A→β1·β2对活前缀αβ1是有效的，其条件是存在规范推导S'*=>aAW=> a β1β2ω。                                                                    （）
4.4.10. SLR(1)文法的特点是：当符号栈中的符号串为βα，而面临的输入符号为α则存在
把α归约为A的规范句型的前缀β Aα时，方可把a归约为A。                  （  ）
综合题
4.5.1请指出图4.2中的LR分析表（a）、（b）、（c）分属LR（0）、SLR和LR（1）中的那一
种，并说明理由。
 
4.5.2文法G的产生式如下：
                            S→BB
                            B～aB|b
    请分别构造该文法的（1) LR (0）分析表；(2）SLR分析表；(3）规范LR分析表（即
LR（1）分析表）；（4）LALR分析表。
 
4.5.3什么是规范句型的活前缀？引进它的意义何在？
 
4.5.4对于文法G[S］：S→AS|b
                  A→SA|a
    (1)列出所有LR (0)项目。
    (2)根据列出的项目构造识别文法活前缀的NFA并确定化为DFAo
  （3)证明DFA的所有状态全体构成文法LR（0)规范族。
 
4.5.5  LR分析器与优先关系分析器在识别句柄时的主要异同是什么？
 
4.5.6  LR（0）、SLR(1), LR（1)及LALR有何共同特征？它们的本质区别是什么？试论述之。
4.5.7 为二义文法G构造一个LR分析表（详细说明构造方法）。其中终结符“，”满足右结合性，终结符“；”满足左结合性，且“，”的优先级高于“；”的优先级。
                      文法G[T]：T→TAT|bTe｝a
                                    A→，|；
 
4.5.8 二义文法G[S],符的优先性和结合性说明如下：
    （a）else与最近的if结合
    (b）“；”优先性大于if
    (c）“；”优先性大于else
    (d)“；”服从左结合
    请使用LR分析法的基本思想，凭借上述条件，为G[S]构造LR分析表，要求写出详细
的构造过程。
                            G[S]:S→if S else S
                                S→if S
                                S→S;S
                                S→a
 
4.5.9 已知文法G[S]为
                    S→aAd|;Bd|aB↑|;A↑
A→a
                    B→a
      （1)试判断G[S]是否为LALR(1)文法。
      (2)当一个文法是LR(1)而不是LALR(1)时，那么LR(1)项目集的同心集合并后会出现哪几种冲突，请说明理由。
 
4.5.10 文法G[T]及其LR分析表（见表4.9)如下，给出串bibi的分析过程。
      （1）T→EbH （2）E→d    （3）E→ε
      （4）H→i  （5）H→Hbi  （6）H→ε
 
4.5.11 给出文法G[S]及图4.9所示的LR(1)项目集规范族中的0、1, 2, 3, 4.
                G[S]: S→S;B|B
                    B→BaA|A
                    A→b(S)
 
 
 
4.5.12 证明AdBd是文法G[S]的活前缀，说明活前缀在LR分析中的作用。给出串dbdb#的LR
分析过程。
                  G[S］： （1）S→AdB    (4) B→b
                          （2）A→a      （5）B--Bdb
                          （3）A→ε    （6）B→ε
 
4.5.13 一个非LR（1）的文法如下：
L→MLb|a
M→ε
请给出所有有移进一归约冲突的LR(1)项目集，以说明该文法确实不是LR(1)的。
 
4.5.14 文法G(S)的产生式集为：
                        S→(EtSeS)|(EtS)|i =E
                          E→+EF|F
                        F→*Fi|i
构造文法G的SLR(1)分析表。要求先画出相应的DFA。
 
4.5.15  下述文法是哪类LR文法？并构造相应分析表。
 
 
4.5.16  给定文法G［A]：A→(A)|a
        （1)证明：LR(1)项目[A→(A·），］］对活前缀“((a”是有效的；
          (2)画出LR(1)项目识别所有活前缀的DFA;
        （3）构造LR(1）分析表；
          (4)合并同心集，构造LALR(1)分析表。
 
4.5.17  已知布尔表达式的方法G[B]如下：
度为G[B]构造LR分析表。
 
4.5.18  8086/8088汇编语言对操作数域的检查可以用LR分析表实现。设m代表存储器，r代表寄存器，i代表立即数；并且为了简单起见，省去了关于m,r,和i的产生式，暂且认为m、r、i为终结符，则操作数域P的文法G如：试构造能够正确识别操作数域的LR分析表。
 
4.5.19 为语言｛amb0|n>m≥0｝写3个文法，它们分别是二义文法、LR(1）文法以及非LR（1)且非二义的文法。不必证明所写文法的正确性，但每个文法的产生式不能超过4个。
 
4.5.20 由文法二义引起的LR(1)分析动作冲突，可以依据消除二义的规则而得到LR(1)分析表，根据此表可以正确识别输入串是否为相应语言的句子。对于非二义非LR(1)文法引起的LR(1)分析动作的冲突，是否也可以依据什么规则来消除LR(1)分析动作的冲突而得到LR(1)分析表，并且根据此表识别相应语言的句子？若可以，是否可以给出这样的规则？
 
4.5.21 有文法G＝（｛S｝，｛a｝，｛S→SaS,S→ε，S），该文法是_____。
        A. LL(l)文法。  B.二义性文法
        C.算符优先文法  D. SLR(1)文法
 
4.5.22 试证明任何一个SLR(1）文法一定是一个LALR(1)文法。
 
4.5.23 文法G[P]：P→aPb|Q
          Q→bQc|bSc
          S→Sa|a
（1)请构造它的SLR分析表，以说明它是不是SLR文法。
(2)在消除左递归、提取公共因子后可得等价文法G[P’］，它是不是LL(1)文法。
 
4.5.24 给出文法G2: S→SaS|SbS|cSd|eS|f
    （1)请证实这是一个二义文法；
    （2)给出什么样的约束条件，可构造无冲突的LR分析表？请证实你的论点。
 
4.5.25  有简单语言的文法G(VT,VN,P,ζ，其中，VT＝｛黑体小写字母串，标点符号，赋值号，运算符｝
      VN＝{P,D,L,S,E,T,B｝
      ζ: P→begin D;S end
            D→id:L
          L→integer|boolean
          S→id:=Elif B then S
          E→E+TIT
              T→id
          B→id|true|false
    （1)试写出该文法的一个句子；
    (2)该文法属于以下哪几种文法，不属于哪几种文法，请说明理由。
      a)上下文无关文法  b) LL(1)文法  c) SLR(1)文法
 
4.5.26  试分析LR(0)、SLR(1), LR(1)和LALR(1)分析表的优缺点。
 
4.5.27 比较LL(K)和LR(K)的异同点。
 
4.5.28  文法G[A］的LR分析表，见表4.21，请给出串ab的分析过程。G[A］的拓广文法为G[A`］。
       
 
4.5.29  文法G[S]及其LR分析表（见表4.22）如下，请给出对串baba#的分析过程。
 
4.5.30 为下面的二义文法G构造一个LR分析表（详细说明构造方法），其中“*”的优先级高于“＋”，且，"*"、“＋”都服从左结合。
                    文法G：E→E+E|E*E|a
 
4.5.31根据程序设计语言的一般要求，为定义条件语句的二义文法G[S]构造SLR(1)分析表，要求写出步骤和必要说明。
                            G[S］：S→iSeS|iS|a
 
4.5.32 对下列文法：
                1）S'→S
                2）S→bRST
                3）S→bR
                4）R→dSa
                5）R→e
                6）T→fRa
                7）T→f
    （1）求各非终结符的FIRST和FOLLOW集合。
    （2）构造该文法的SLR(1)分析表。（请将终结符和非终结符以abdef#SRT顺序构造分
析表）
 
4.5.33 下述文法是SLR文法吗？若是，给出分析表；否则，说明理由。
      （1）S→bASB|bA
      （2）A→dSa|e
      （3）B→cAa|c
   
4.5.34  己知某语言L={ambn|n>m≥0}。试写出产生该语言的两种文法G1和G2,其中G1是
LR(1)文法，G2是非LR(1)和非二义性文法。
 
4.5.35 构造一个LR(1）文法G,它产生语言L（G）={w}w|(a|b)*，w中a和b的个数相等｝。
 
4.5. 36 试证明任何的SLR(l)文法都是LR(1)文法。
 
4.5.37 给定拓广文法G (S为G的开始符号），G的产生式（附带编号）如下：
                                  0）S→E
                                  1）E→E+T
                                  2）E→T
                                  3）T→i
                                  4）T→(E)
(1)构造文法G的LR(1)项目集规范族和GO函数。
（2）构造G的LR(1）分析表。
5
※<习题五>
第五章  中间代码生成
5．1 单项选择题
1．中间代码生成时所依据的是—。
        a．语法规则  b．词法规则  c．语义规则  d．等价变换规则
    2．四元式之间的联系是通过___实现的。
        a．指示器  b．临时变量  c．符号表    d．程序变量
    3．后缀式ab+cd+/可用表达式___来表示。（陕西省1999年自考题）
        a． a+b/c+d  b． (a+b)/(c+d)    c． a+b/(c+d)  d． a+b+c/d
    4．间接三元式表示法的优点为＿。（陕西省1998年自考题）
        a．采用间接码表，便于优化处理    b．节省存储空间，不便于表的修改
        c．便于优化处理，节省存储空间    d．节省存储空间，不便于优化处理
    5．表达式(A∨B)∧(C∨D)的逆波兰表示为＿。（陕西省1998年自考题）
        a．┐AB∨∧CD∨    b． A┐B∨CD∨∧
        c． AB∨┐CD∨∧      d． A┐B∨∧CD∨                     
  　6．中间代码的树型表示        所对应的表达式为___。（陕西省1998年自考题）
        a． A+B+C+D  b． A+(B+C)+D  c．（A+B)+C+D    d． (A+B)+(C+D)
    7．四元式表示法的优点为＿。（陕西省1997年自考题）
        a．不便于优化处理，但便于表的更动b．不便于优化处理，但节省存储空间
        c．便于优化处理，也便于表的更动d．便于表的更动，也节省存储空间
    8．终结符具有＿属性。
        a．传递  b．继承  c．抽象  d．综合
    9．有文法G及其语法制导翻译如下所示（语义规则中的*和＋分别是常规意义下的算术运算符）：
                E→E'∧T｛E．val：=E'．val*T．val}
                E→T｛E．val：=T．val}
                T→T'#n｛T．val：=T'．val+n．val｝
                T→n {T．val：=n．val;}
则分析句子1∧2∧3#4其值为＿。          　（西安电子科大2000年研究生试题）
a．    10  b． 34  c． 14  d． 54
10．表达式（a+b)*c的后缀式表示为＿。
          a． ab*c+    b． abc*+    c． ab+e*    d． abc+*
    11．后缀式＿对应的表达式是a-(-b)*c（＠代表后缀式中的求负运算符）。
        a． a-b@c*、b． ab＠．c． ab@c-* d, ab@c*-
    12．使用___可以把Z=(X+0．418）＊YNV翻译成四元式序列。（陕西省1999年自考题）
        a．语义规则  b．等价变换规则  c．语法规则  d．词法规则
    13．采用右结合规则时，a+b*c+d可解释为＿（假设*的优先级高于＋）。
                                                        （陕西省2000年自考题）
        a． (a+(b*c))+d        b． a+((b*c)+d)      c． a+d+(b*c)  d． (b*c)+a+d
    14．更动一张＿表很困难。（陕西省2000年自考题）
        a．三元式  b．间接三元式  c．四元式  d．三元式和四元式
    15．有一语法制导翻译如下所示：      　（西安电子科大1999年研究生试题）
                  S→bAb {print"1"}
                  A→(B {print"2"}
                  A→a    {print"3"}
                  B→Aa) {print"4"}
若输入序列为b(((aa)a)a)b,且采用自下而上的分析方法，则输出序列为＿。
          a. 32224441  b. 34242421  c. 12424243  d. 34442212
5.2　多项选择题
    1．中间代码主要有___。
      　a.四元式  b.二元式  c.三元式  d.后缀式  e.间接三元式
2.下面中间代码形式中，能正确表示算术表达式a+b+c的有＿。（陕西省1997年自考题）
3.在下面的＿语法制导翻译中，采用拉链一回填技术。
      a.赋值语句    b.布尔表达式的短路计算  c. goto语句
      d.条件语句  e.循环语句
4.下列___中间代码形式有益于优化处理。（陕西省1997年自考题）
    a.三元式  b.四元式  c.间接三元式  d.逆波兰表示法  e.树形表示法
5.在编译程序中安排中间代码生成的目的是＿。
      a.便于进行存储空间的组织  b.利于目标代码的优化
      c.利于编译程序的移植    d.利于目标代码的移植
      e.利于提高目标代码的质量
6.下面的中间代码形式中，＿能正确表示算术表达式a+b*c。（西省2000年自考题）
  　7.三地址代码语句具体实现通常有＿表示方法。
        a.逆波兰表示  　b.三元式    　c.间接三元式    d.树形表示    e.四元式
5.3　填空题
1.中间代码有______等形式，生成中间代码主要是为了使______。
    2.语法制导翻译既可以用来产生＿代码，也可用来产生＿指令，甚至可用来对
输入串进行。（陕西省1999年自考题）
    3.当源程序中的标号出现“先引用后定义”时，中间代码的转移地址须待____时才能
确定，因而要进行____。（陕西省1998年自考落）
    4.文法符号的属性有两种，一种称为____，另一种称为_____。
    5．后缀式abc-/所代表的表达式是＿，表达式(a-b)*c可用后缀式＿表示。  （陕西省2000年自考题）
    6.用一张______辅以_____的办法来表示中间代码，这种表示法称为间接三元式。
7.在语法分析中，根据每个产生式对应的语义子程序进行____的办法叫做____。
                                                        （陕西省1998年自考题）
    8.对＋、*采用左结合习惯，对乘幂↑个采用右结合习惯，则E1+E2+E3可解释成＿，
而E1↑E2↑E3可解释成＿。（陕西省1997年自考题）
    9.在语法树中，一个结点的综合属性的值由其＿的属性值确定，而继承属性则由该
结点的＿的某些属性确定。
    10.对某个压缩了的上下文无关文法，当把每个文法符号联系于，且让该文法的规
则附加以＿时，称该文法为属性文法。
11.语法制导的翻译程序能够同时进行_____和______。
5.4 判断题
1.一个语义子程序描述了一个文法所对应的翻译工作。（）
    2.逆波兰表示法表示表达式时无须使用括号。  　（）
3.树形表示和四元式不便于优化，而三元式和间接三元式则便于优化。（）
    4.三地址语句类似于汇编语言代码，可以看成中间代码的一种抽象形式。（）
    5.非终结符可以有综合属性，但不能有继承属性。（）
    6.程序中的表达式语句在语义翻译时不需要回填技术。（）
    7.在编译阶段只对可执行语句进行翻译。（）
    8.无论是三元式表示还是间接三元式表示的中间代码，其三元式在三元式表中的位置一
旦确定就很难改变。（陕西省1998年自考题）（）
9.对中间代码的产生而言，目前还没有一种公认的形式系统。（）
    10.三元式出现的先后顺序和表达式各部分的计值顺序并不一致。（）
    11.自上而下分析的一个优点是：在一个产生式的中间就可以调用语义子程序。（）
    12.终结符只有继承属性，它们由词法分析器提供。（）
    13.翻译算术表达式语句时需要用到回填技术。（）
14.程序中不允许标号先引用后定义。（）
5.5 综合题
5.5 .1                  （哈工大2000年研究生试题）
叙述下列概念：
    （1）语法制导翻译 (2)翻译文法 (3)语义子程序
5.5.2                （武汉大学1999年研究生试题）
何谓“语法制导翻译(SDTS)”？试给出用SDTS生成中间代码的要点，并用一简例予以说明。
5.5.3  给出下列表达式的逆波兰表示(后缀式)：
      ①a*(－b+c)
      ②(A∨)∧(C∨┐D∧E)
      ③if (x+y)*Z=5 then x：=(a+b)↑c else y：=a↑b↑ c
5.5.4  写出算术表达式：A+B*(C－D)+E/(C－D)↑N的
      ①四元式序列；②三元式序列；③间接三元式序列；④树形表示
5.5.5              （清华大学1999年研究生试题）
    令S.val为文法G[S]生成的二进制数的值，例如对输入串101．101则S.val=5.625。按照语法制导翻译方法的思想，给出计算S.val的相应的语义规则。
                G[S]：S-L.L|L
                      L→LB|B
                      B→0|1
5.5.6                            （清华大学2000年研究生试题）
    现有文法G1、G2如下，欲将G1定义的expression转换成如、G2的E所描述的形式。给出其语法制导翻译的语义描述。（提示：可采用类似yacc源程序的形式，所涉及的语义函数须用自然语言给予说明，不用抄写产生式，用产生式编号表示）。
    G1：(1)<program>→<decl statement>：begin <statement list> end.
        （2）<decl statement>→var<iddecl>
        （3）<iddecl>→<iddecl>,id：<type decl>
        （4）<iddecl>→id：<type decl>
        （5）<type decl>→int
        （6）<type decl>→bool
        （7）<statement list>→<expression>
        （8）<statement list>→<statement list>；<expression>
        （9）<expression>→<expression> and <expression>
      　（10）<expression>→<expression>*<expression>
        （11）<expression>→id
        （12）<expression>→num
        （13）<expression>→true
        （14）<expression>→false
要求：（1) <expression>中的id必须在<decl statement>中先声明。
      (2)and和*分别是常规的布尔和算术运算符，要求其运算对象的相应类型匹配，
    G2：E→EE*|EE and|id|num|true|false
5.5.7      下面的文法生成变量的类型说明：
            D→id L
            L→,id L|:T
            T→integer|real
试构造一个翻译方案，仅使用综合属性，把每个标识符的类型填入符号表中（对所用到
的过程，仅说明功能即可，不必具体写出）。
5.5.8  已知文法G及每个产生式相应的语义子程序如下：
      （1）E→i {E·TC: =NXQ; E·FC:=NXQ+1：GEN (jnz, ENTRY(i), ,0);
        GEN (j,＿,＿,0)}/*NXQ指针总是指向下一个将要形成的四元式的地址（编号）；
GEN过程把四元式（OP, ARG1，ARG2，RESULT）填入四元式表中*/
      (2)E→i(1)ropi(2) {E·TC: =NXQ; E·FC:=NXQ+1：GEN(jrop, ENTRY(i(1)),ENTRY(i(2)),0);
        GEN (j,＿,＿,0)}/*jrop是根据关系符rop而定义的一条件转移指令*/
      (3）E→(E(1)) {E·TC:=E(1)·TC；E·FC:＝E(1)·FC}
      (4)E→┐E(1)  {E·TC:=E(1)·FC；E·FC:＝E(1)·TC}
    （5）EA→E(1)∧{BACKPATCH(E(1)·TC，NXQ)；EA·FC:=E(1)·FC}
          /*BACKPATCH过程将NXQ的当前值填入E(1)·TC所指四元式的第四区段*/
    （6）E→EAE(2) {E·TC:=E(2)·TC；E·FC: =MERG（EA·FC，E(2)·FC)}
          /*MERG函数将EA·FC和E(2)·FC两条链合并，并以EA·FC作为链首*/
    （7）E0→E(1)∨{BACKPATCH(E(1)·FC，NXQ)；E0·TC:=E(1)·TC}
    （8）E→E0E(2) {E·FC:=E(2)·FC；E·TC:=MERG(E0·TC, E(2)·TC}
5.5.9  赋值语句的文法及语义动作描述如下：
(1)A→:=E {GEN(:=,E·PLACE,＿ ,ENTRY(i))}
(2)E→E(1)+E(2) {E·PLACE:=NEWTEMP：GEN(＋，E(1))·PLACE,E(2)·PLACE,E·PLACE)}
(3)E→E(1)*E(2) {E·PLACE:=NEWTEMP：GEN(*，E(1)·PLACE,E(2)·PLACE,E·PLACE)}
(4)E→-E(1) {E·PLACE:=NEWTEMP：GEN(＠，E(1)·PLACE,＿,E·PLACE)}
(5)E→(E(1)  {E·PLACE:= E(1)·PLACE}
(6)E→i  {E·PLACE:=ENTRY(i)}
写出赋值语句X:=-B*(C+D)+A的自下而上的语法制导翻译过程。
5.6.0    (1)写出Pascal语言的repeat语句；
                repeat
                S1；S2；…；Sn
                until. E；
的文法及对应的语义子程序(注：E为条件表达式)；
        (2)按构造好的文法分析并翻译语句：
                                  repeat
                                    x：=x+l
                                  until x>5；
5.6.1          写出翻译过程调用语句的语义子程序。要求生成的四元式序列在转子指令之前的参数四元式par按反序出现（与实在参数的顺序相反），问这种情况下在翻译过程调用语句时是否需要语义变量（队列）QUEUE呢？
5.6.2          （国防科大2001年研究生试题）
    设某语言的while语句的语法形式为：
              S→while E do S(l)
其语义解释如图5.8所示。
    (1)写出适合语法制导翻译的产生式。
(2)写出每个产生式对应的语义动作。
5.6.3                              (国防科大1999年研究生试题) 
条件式if E(l) then E(2) else E(3)的语义解释为：若布尔式E(l)为真，则条件表达式值取E(2)的值；否则条件表达式值取E(3)的值。
    (1)写出if E(l) then E(2) else E(3)的适合语法制导翻译的产生式及相应语义子程序。
    (2)按(1)中的语义子程序把
                                a:=if x>0 then x+1 else x+2;
翻译为四元式序列。
5.6.4                                                (哈工大2000年研究生试题)
设for语句的形式为：
                          for V=El step E2 until E3 do S
请设计其目标结构，并给出相应的语义分析过程。
5.6.5  某程序设计语言中有如下形式的选择语句
          switch (E)
              {case cl：sl；
                      case c2：s2；
                        case ci：si；
                      case cn：Sn；
                  default： Sn+l
              }
其中n≥1。此选择语句的语义是：先计算整型表达式E的值，然后将表达式的值依次和case
后的常数Ci比较，当与某常数ci相等时就执行语句Si, 并结束该选择语句； 若与诸常数均不相等, 则执行语句Sn+1。
    为了便于翻译, 上述选择语句可用下列产生式来定义：
                A→switch(E)
                  B→A{case c
                  D→B：S|F：S
                  F→D；case c
                S→D；default：S}
  使用自上而下的语法制导翻译方法,给出翻译此选择语句的翻译子程序(语义子程序)。
  在翻译子程序中可以使用下列指示器、过程和函数，
    ·指示器NXQ：指向下一个将要形成但尚未生成的四元式的地址；
    ·过程GEN(OP,ARG1,ARG2,RESULT),该过程把四元式
                            (OP,ARG1,ARG2,RESULT)
填进四元式表中，且将NXQ增加1；
    ·过程BACKPATCH(P,t)：把P所链接的每个四元式的第四区段都填为t；
    ·函数MERG(P1, P2)：把P1和P2为链首的两条链合并,回送合并后的链首；
·函数ENTRY(i)：回送标识符i在符号表中的位置。
5.6.6  含有数组元素的赋值语句翻译规则如下：
  ①A→V：=E    {IF V·OFFSET=null THEN GEN(：=,E·PLACE,_,V·PLACE)
                                                          /*V为简单变量*/
                ELSE GEN([]＝,E·PLACE,_V·PLACE[V·OFFSET])      /*V为数组变量*/}
  ②E→E(1)+E(2)  {T：=NEWTEMP；GEN(+，E(1)·PLACE，E(2)·PLACE,T)；E·PLACE：=T)
  ③E→(E(1))    {E·PLACE：＝E(1)·PLACE)
  ④E→V        {IF V·OFFSET=null THEN E·PLACE：=V·PLACE
                                                              /*V为简单变量*/
                ELSE BEGIN T：=NEWTEMP； GEN(＝[],V·PLACE[V OFFSET],_,T)；
                E·PLACE：=T END /*V为数组变量*/}
  ⑤V→elist]    {T：=NEWTEMP；GEN(-,elist·ARRAY,C,T)；
                /*elist·ARRAY为数组的首地址a, C为常数：d2d3… dn+d3 …dn+…+dn+1*/
                V·PLACE：=T； V·OFFSET：=elist·PLACE}
  ⑥V→i        {V·PLACE：=ENTRY(i)：V·OFFSET：=null}
                                        /*V·OFFSET为null表示V为简单变量*/
  ⑦elist→elist(1),E {T：=NEWTEMP；k：=elist(1).DIM+1；/*下标记数，初值elist(l).DIM=1*/
                  dK：=LIMIT(elist(l).ARRAY,K)；/*给出数组第K维的长度*/
                  GEN (*,elist(l).PLACE,dK,T)； GEN(+,E·PLACE,T,T)；
                  elist·ARRAY：=elist(l).ARRAY； elist·PLACE：=T； elist·DIM：=K}
  ⑧elist→i[E    {elist·PLACE：=E·PLACE；elist·DIM：=1；elist·ARRAY：=ENTRY(i)
                                /*ENTRY(i)为数组i的入口地址(即首地址a)*/}
    己知A是一个10X20的数组且按行存放,求： (1)赋值语句X：=A[I,J]的四元式序列；
(2)赋值语句A[I+2, J+1]： =M+N的四元式序列。
5.6.7  改写例题5.12文法G描述布尔表达式的语义子程序,使得i(1)rop i(2)不按通常方式翻译为下面的相继两个四元式：
                      (jrop, i(1), i(2), 0)
                        (j_,_,0)
而是翻译成如下的一个四元式：
                (jnrop, i(1), i(2), 0)
使得当iMrop i(2)为假时发生转移，而为真时并不发生转移(即顺序执行下一个四元式),从而
产生效率较高的四元式代码。
5.6.8                            (上海交大2000年研究生试题)
    给出文法G[S]：S→-SaA|A
                  A→AbB|B
                  B→cSd|e
    （1)请证实AacAbcBaAdbed是文法G[S]的一个句型。
    (2)请写出该句型的所有短语、素短语以及句柄。
    (3)为文法G[S]每个产生式写出相应的翻译子程序，使句型AacAbcBaAdbed经该翻译
方案后，输出131********0。
  (4)文法G[S]是不是SLR文法？请构造分析表证实之。
5.6.9                                              (上海交大2000年研究生试题)
    语句While A<B do if C>D then x:=F[i,j] else x:=x+l经翻译后的三地址语句或四元式是
什么？（设三地址语句或四元式自100开始存放，数组F的内情向量自300开始存放，数组首地址500,每个数组元素占四字节。）
5.7.0        (上海交大1997年研究生试题)
    文法G及相应的翻译方案如下
  S→bts{printf:"1")
                        S→a {print: "2"}
                        T→R {print: "3"}
                        R→R/S {print: "4"}
                          R→S {print: "5"}
    (1）文法G属于Chomsky哪一型文法？
    (2)符号串bR/bTc/bSc/ac是不是该文法的一个句型，请证实。
  （3)若是句型，写出该句型的所有短语、素短语以及句柄。
    (4)文法G是不是算符优先文法，请予证实。
  （5)文法G经消除左递归后得到的等价文法G’是不是LL(1)文法，请予证实。
    (6)文法G是不是SLR(1)文法，请予以证实。
(7)对于题2的输入符号串，该翻译方案的输出是什么？
5.7.1      下面是用筛选法求素数的程序段，试将其翻译为四元式序列。
                    for i：=2 to N do
                  B [i]：=true；
                  i：=1；
                  while i≤N do
                  begin
                        i：=i+l；
                    if B[i]then
                      begin
                          j：=2；
                        while i*j≤N do
                            begin
                            B[i*j]：=false
                                j：=j+1
                                        end
                                end
                          end；
5.7.2          使用中间语言有什么好处？
5.7.3  将下面的语句翻译成四元式序列：
            while A<C∧B<D do
                if A=1 then C:=C+l
                else while A≤ D do
                  A:=A+2；
5.7.4                      （陕西省1999年自考） 
已知源程序如下：       
                prod:=0;
                  i=1；
                    WHILE i≤20 do
                  begin
                    prod:=prod+a[i]*b[i]；
                                i=i+l
                        end；
试按语法制导翻译法将上述源程序翻译成四元式序列（设A是数组a的起始地址，B是数组b的起始地址；机器按字节编址，每个数组元素占四个字节）。
5.7.5          (中科元计算所1999年研究生试题)
己知表达式为A+B*(C-D）**N（**为幂乘）
（1)给出该表达式的逆波兰式表示（后缀式）。
(2）给出上述表达式的四元式和三元式序列。
5.7.6      (中科元计算所1999年研究生试题)
文法G的产生式如下：
                    S→(L)|α
                      L→L，S|S
（1)试写出一个语法制导定义，它输出配对括号个数。
(2）写一个翻译方案，打印每个a的嵌套深度。如((a), a),打印2,1。
5.7.7                      (中科元计算所2000年研究生试题)
程序的文法如下：
                    p→D
              D→D；D|id:T|proc id；D；S
（1)写一个语法制导定义，打印该程序一共声明了多少个id?
(2）写一个翻译方案，打印该程序每个变量id的嵌套深度。
5.7.8                              (南开大学1998年研究生试题)
    写出语句
              X:=(a+b)*c
              Y=d↑（a+b)
的间接三元式。
5.7.9                            (国防科大1999年研究生试题)
    把语句if a>b then while x>0 do x:=x-2
          else y:=y+1；
翻译为四元式序列。
5.8.0                            (国防科大1999年研究生试题)
把下面的语句
      while (A>B) do
            if (C<D) then X：=Y*Z
                      else X：=Y+Z
翻译成四元式。
5.8.1举例说明什么是语法制导的翻译。
5.8.2  对下面的程序段，产生相应的四元式，并给出填符号表、返填、拉链等过程的执行情况。
        GOTO L1；
          S1；
        GOTO L1；
        S2；
        COTO L1；
  L1： S3；
        GOTO Ll；
  L2： S4；
        GOTO L2；
        S5；
    文法G[P]↑及相应翻译方案为
                          p→bQb {print：”1”}
                          Q→cR {print：“2”}
                          Q→a {print： "3"}
                          R→Qad {print： "4"}
    (1)该文法是不是算符优先文法，请构造算符优先关系表证实之。
    (2)输入串为bcccaadadadb时，该翻译方案的输出是什么？
5

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。