编译原理总温习1

  请写出Chomcky关于文法的界说。 关于文法的界说。 五、*请写出 请写出 关于文法的界说 Chomcky文法的界说：文法G界说为四元组 记 文法的界说：文法 界说为四元组 界说为四元组,记 文法的界说 为: G=(VN,VT,P,S) 其间： 其间：VN —非空有限的非完结符号集 非空有限的非完结符号集 VT —非空有限的完结符号集 非空有限的完结符号集 P — 发生式集 S — 开始符号 辨认符号 开始符号/辨认符号 S∈ VN ∈

  十三、确认的有穷主动机 十三、确认的有穷主动机DFA和不确认的有穷主动机 和不确认的有穷主动机 NFA 的概念，对每个 的概念，对每个NFA N必定存在一个 必定存在一个DFA M， 必定存在一个 ， 使得L(M)=L(N)。对每个 使得 。对每个NFA N存在着与之等价的 存在着与之等价的 DFA M。与某一 等价的DFA不仅有。 ε-闭包和 不仅有。 闭包和 。与某一NFA等价的 等价的 不仅有 子集法算法将NFA转化成承受相同的言语的 转化成承受相同的言语的DFA。 子集法算法将 转化成承受相同的言语的 。 十四、语法剖析是编译程序的中心部分。 十四、语法剖析是编译程序的中心部分。语法剖析的 作用是辨认由词法剖析给出的单词符号序列是否是给 定文法的正确语句(程序 程序)， 定文法的正确语句 程序 ，现在语法剖析常用的办法 有自顶向下（自上而下）剖析和自底向上（自下而上） 有自顶向下（自上而下）剖析和自底向上（自下而上） 剖析两大类。 剖析两大类。

  请解说编译程序的前端和后端的概念， 二、*请解说编译程序的前端和后端的概念，试问前 请解说编译程序的前端和后端的概念 端一般包含那些阶段，后端包含那些阶段？ 端一般包含那些阶段，后端包含那些阶段？ 编译程序的前端只依赖于源言语， 编译程序的前端只依赖于源言语，由简直独立于 方针机器的阶段或阶段的一部分组成。 方针机器的阶段或阶段的一部分组成。编译程序的前 端一般包含词法剖析程序、语法剖析程序、 端一般包含词法剖析程序、语法剖析程序、语义剖析 程序、 程序、中心代码生成程序及相关的表格管理程序和出 错处理程序。 错处理程序。编译程序的后端是指编译器中依赖于目 标机器的部分,它们一般独立于源言语 它们一般独立于源言语， 标机器的部分 它们一般独立于源言语，而与中心代 码有关。一般包含方针代码生成程序、 码有关。一般包含方针代码生成程序、代码优化程序 和相关的表格管理程序和犯错处理程序。 和相关的表格管理程序和犯错处理程序。

  十八、猜测剖析办法是自顶向下剖析的办法， 十八、猜测剖析办法是自顶向下剖析的办法，一个预 测剖析器是由三个部分所组成。 测剖析器是由三个部分所组成。 · 猜测剖析程序 总控程序 猜测剖析程序(总控程序 总控程序) · 先进后出栈(stack) 先进后出栈 · 猜测剖析表：猜测剖析表以完结符号和“#” 猜测剖析表：猜测剖析表以完结符号和“ 号作为列标志，以非完结符号作为行标志， 号作为列标志，以非完结符号作为行标志，对每个 完结符号或“ 号用 标明， 号用a标明 完结符号或“#”号用 标明，若a∈SELECT(A→α), ∈ 则把A→α放入 放入M[A,a]中,把所有无界说的 把所有无界说的M[A,a]标 则把 放入 中 把所有无界说的 标 上犯错符号。这就构成了猜测剖析表。 上犯错符号。这就构成了猜测剖析表。 要求学员可以对一个给定的文法判别是否是 LL(1)文法；能结构猜测剖析表；能用猜测剖析方 文法；能结构猜测剖析表； 文法 法判别给定的输入符号串是否是该文法的语句。 法判别给定的输入符号串是否是该文法的语句。 根本要求） （根本要求）

  十、程序设计言语的单词符号一般可分红下列5种： 程序设计言语的单词符号一般可分红下列 种 保留字，也称关键字。 ① 保留字，也称关键字。 标识符，用来标明各种姓名，如常量名、 ② 标识符，用来标明各种姓名，如常量名、变 量名和进程名等。 量名和进程名等。 常数，许多类型的常数， ③ 常数，许多类型的常数，如25，3.1415， ， ， TRUE和“ABC”等。 和 等 运算符， ④ 运算符，如，*，=等。 ，， 等 界符，如逗点，分号，括号等。 ⑤ 界符，如逗点，分号，括号等。

  四、阐明语法的一个东西是文法，这是方式言语理 阐明语法的一个东西是文法， 论的根本概念之一。当咱们表述一种言语时， 论的根本概念之一。当咱们表述一种言语时，无非 是阐明这种言语的语句， 是阐明这种言语的语句，假如言语只含有有穷多个 语句，则只需列出语句的有穷集就行了， 语句，则只需列出语句的有穷集就行了，但关于含 有无量语句的言语来讲， 有无量语句的言语来讲，存在着怎么给出它的有穷 标明的问题。事实上，运用文法作为东西，不仅为 标明的问题。事实上，运用文法作为东西， 了严格地界说语句的结构， 了严格地界说语句的结构，也仍是为了用恰当条数的 规矩把言语的悉数语句描绘出来， 规矩把言语的悉数语句描绘出来，是以有穷的调集 刻划无量的调集的东西。 刻划无量的调集的东西。 在方式上言语是符号串的调集。 在方式上言语是符号串的调集。符号串是由字 母表中的符号所组成的任何有穷序列。 母表中的符号所组成的任何有穷序列。符号串的运 算和符号串调集的运算。 乘积、方幂与闭包。 算和符号串调集的运算。和、乘积、方幂与闭包。

  十一、程序设计言语的单词可用正规文法描绘。 十一、程序设计言语的单词可用正规文法描绘。正 规文法是右线性文法,文法 文法G=(VN,VT,P,S), P中的每 中的每 规文法是右线性文法 文法 一条规矩形为A→aB或A→a,其间 其间A,B∈VN ,a∈VT 。 一条规矩形为 或 其间 ∈ ∈ 正规文法所描绘的是VT上的正规集（正规文法描绘 正规文法所描绘的是 上的正规集（ 的言语的语句的调集）。正规式也称正则表达式， ）。正规式也称正则表达式 的言语的语句的调集）。正规式也称正则表达式， 也是标明正规集的数学东西。 也是标明正规集的数学东西。正规式阐明单词的模 也便是阐明单词组成的方式规矩， 式，也便是阐明单词组成的方式规矩，正规集则是 满意这些规矩的单词的调集。 满意这些规矩的单词的调集。 十二、 确认的有穷主动机也称有限主动机 确认的有穷主动机也称有限主动机， 十二、*确认的有穷主动机也称有限主动机，它是作 为一种辨认设备，它能精确地辨认正规集， 为一种辨认设备，它能精确地辨认正规集，即辨认 正规文法所界说的言语和正规式所标明的调集。 正规文法所界说的言语和正规式所标明的调集。具 体而言， 体而言，一个确认的有穷主动机可以用一个五元组 标明， 是一个有穷状况集， 标明，即M=(K,Σ,f, S,Z)。K是一个有穷状况集，Σ 。 是一个有穷状况集 是一个有穷字母表， 是转化函数 是转化函数， 是初态 是初态， 是一 是一个有穷字母表，f是转化函数，S是初态，Z是一 个终态集。 个终态集。

  十五、自顶向下剖析法也称面向方针的剖析办法， 十五、自顶向下剖析法也称面向方针的剖析办法， 也便是从文法的开始符号动身妄图推导出与输入的 单词串彻底相匹配的语句， 单词串彻底相匹配的语句，若输入串是给定文法的 语句，则必能推出，反之必定犯错。 语句，则必能推出，反之必定犯错。自顶向下剖析 法又可分为确认的和不确认的两种， 法又可分为确认的和不确认的两种，确认的剖析方 法需对文法有必定的约束，但由于完成办法简略、 法需对文法有必定的约束，但由于完成办法简略、 直观，便于手艺结构或主动生成语法剖析器， 直观，Hale Waihona Puke Baidu于手艺结构或主动生成语法剖析器，因此 仍是现在常用的办法之一。 仍是现在常用的办法之一。不确认的办法即带回溯 的剖析办法， 的剖析办法，这种办法其实便是一种穷举的打听方 因此功率低，代价高，因此很少运用。 法，因此功率低，代价高，因此很少运用。在确认 的自顶向下语法剖析顶用的是最左推导。 的自顶向下语法剖析顶用的是最左推导。

  根本概念题： （一） 根本概念题： 一、*编译程序的概念 编译程序的概念 编译程序是现代计算机体系的根本组成部分之一。 编译程序是现代计算机体系的根本组成部分之一。 简而言之, 编译程序便是一种言语翻译程序 便是一种言语翻译程序。 简而言之 编译程序便是一种言语翻译程序。所谓翻 译程序，是指这样一个程序，它能将高档程序设计语 译程序，是指这样一个程序， 言程序翻译成逻辑等价的低级言语(汇编言语, 言程序翻译成逻辑等价的低级言语(汇编言语,机器语 程序。编译程序一般由词法剖析程序、 言) 程序。编译程序一般由词法剖析程序、语法剖析 程序、语义剖析程序、中心代码生成程序、 程序、语义剖析程序、中心代码生成程序、方针代码 生成程序、代码优化程序、 生成程序、代码优化程序、表格管理程序和犯错处理 程序等成分构成。 程序等成分构成。

  请阐明有关标准句型的概念？ 八、*请阐明有关标准句型的概念？ 请阐明有关标准句型的概念 最右推导， 答：最右推导，即推导的每一步都是替换当时 句型最右边的非完结符，被称为标准推导， 句型最右边的非完结符，被称为标准推导，由标准 推导得到的句型称为标准句型。 推导得到的句型称为标准句型。

  九、简略阐明词法剖析程序的主要任务。 简略阐明词法剖析程序的主要任务。 词法剖析程序是编译程序的一个构成成分， 答：词法剖析程序是编译程序的一个构成成分， 它的主要任务是扫描源程序，按构词规矩辨认单词， 它的主要任务是扫描源程序，按构词规矩辨认单词， 并报告发现的词法过错。 并报告发现的词法过错。

  三、言语的语法描绘 言语的语法描绘办法有其三， 言语的语法描绘办法有其三，用自然言语描绘 言语的语法， 言语的语法，用语法图描绘言语的语法和用巴科斯 -瑙尔范式及扩大的巴科斯 瑙尔范式 (EBNF)两种 瑙尔范式及扩大的巴科斯-瑙尔范式 瑙尔范式及扩大的巴科斯 两种 方式给出言语的语法描绘。 方式给出言语的语法描绘。 用语法图描绘言语的语法与EBNF描绘相比较： 描绘相比较： 用语法图描绘言语的语法与 描绘相比较 语法图描绘： 直观，易读，易写。 语法图描绘： 直观，易读，易写。 EBNF标明：方式化强，易机器辨认。 标明： 标明 方式化强，易机器辨认。

  十七、 文法： 文法的意义是： 十七、LL(1)文法： LL(1)文法的意义是：第一个 文法 文法的意义是 第一个L 标明自顶向下剖析是从左向右扫描输入串，第二 标明自顶向下剖析是从左向右扫描输入串， 标明剖析进程中将用最左推导， 标明只需向 个L标明剖析进程中将用最左推导，1标明只需向 标明剖析进程中将用最左推导 右看一个符号便可决议挑选哪个发生式或规矩进 行推导。 （ ）办法是LL（ ）办法的特例。 行推导。LL（1）办法是 （K）办法的特例。 一个上下文无关文法是LL(1)文法的充沛必要条件 一个上下文无关文法是 文法的充沛必要条件 对每个非完结符A的两个不同发生式 的两个不同发生式， 是：对每个非完结符 的两个不同发生式，A→α, A→β,满意 满意 SELECT(A→α)∩SELECT(A→β)=Φ 其间α， 不一起能 不一起能ε 其间 ，β不一起能

  六、*例：已知文法： E→XEX 例 已知文法： X→YX*Y Y→（E）i （ ） 请断定该文法是那类文法？ 请断定该文法是那类文法？ 文法的界说， 答：依据 Chomcky文法的界说，该文法是 类文 文法的界说 该文法是2类文 即上下文无关文法。 法，即上下文无关文法。 七、*请阐明有关句型、语句、句柄概念？ 请阐明有关句型、 请阐明有关句型 语句、句柄概念？ 是一文法， 答：设G[S]是一文法，假如符号串 是从文法的 是一文法 假如符号串x是从文法的 辨认符号推导出来的，则称符号串x是文法 是文法G[S]的句 辨认符号推导出来的，则称符号串 是文法 的句 若符号串x还满意仅由完结符号组成的条件 还满意仅由完结符号组成的条件， 型。若符号串 还满意仅由完结符号组成的条件，则 的语句。 称x为G[S]的语句。一个句型的最左直接短语称为该 为 的语句 句型的句柄。 句型的句柄。

  十六、 请阐明有关猜测符号集的概念 请阐明有关猜测符号集的概念？ 十六、*请阐明有关猜测符号集的概念？ 猜测符号集标明： 答：发生式A→α猜测符号集标明：在确认的自上 发生式 猜测符号集标明 而下的语法剖析进程中，当需求替换的非完结符是A 而下的语法剖析进程中，当需求替换的非完结符是 而当时需求匹配的完结符归于发生式A→α猜测 时，而当时需求匹配的完结符归于发生式 猜测 符号会集的符号，则可以选用该发生式进行推导。 符号会集的符号，则可以选用该发生式进行推导。当 α不能推出 时，发生式 不能推出ε时 发生式A→α猜测符号集是 的首符号 猜测符号集是α的首符号 不能推出 猜测符号集是 能推出ε时 发生式A→α猜测符号集是 的首 猜测符号集是α的首 集；当α能推出 时，发生式 能推出 猜测符号集是 符号集与A的后跟符号集的并集 可是不包含ε。 的后跟符号集的并集， 符号集与 的后跟符号集的并集，可是不包含 。