简单算术表达式的结构可以用下面的上下文无关文法进行描述(E为开始符号)，（50）是符合..

免费智能真题库 > 历年试卷 > 软件设计师 > 2018年上半年软件设计师上午试卷综合知识

第50题

知识点：文法和语言的形式描述上下文无关文法文法

关键词：表达式开始符号上下文无关文法文法章/节：计算机软件知识

简单算术表达式的结构可以用下面的上下文无关文法进行描述(E为开始符号)，（50）是符合该文法的句子。
    E→T|E+T
    T→F|T*F
    F→-F|N
    N→0|1|2|3l4|5|6|7|8|9

A. 2--3*4

B. 2+-3*4

C. (2+3)*4

D. 2*4-3

相关试题：编译程序的基本原理

更多>

第49题 2017年下半年

某确定的有限自动机（DFA）的状态转换图如下图所示（0是初态，4是终态），则该DFA能识别（）。

第22题 2014年下半年

51%

将高级语言源程序翻译成机器语言程序的过程中，常引入中间代码。以下关于中间代码的叙述中，不正确的是（）。

第48题 2016年上半年

52%

移进—归约分析法是编译程序（或解释程序）对高级语言源程序进行语法分析的一种方法，属于（48）的语法分析方法。


知识点讲解
· 文法和语言的形式描述 · 上下文无关文法 · 文法

文法和语言的形式描述

1）文法的定义

描述语言语法结构的形式规则称为文法。文法G是一个四元组，可表示为G=(V_N,V_T,P,S)，其中V_T是一个非空有限集，其中的每个元素称为一个终结符；V_N是一个非空有限集，其每个元素称为非终结符。V_N∩V_T=?。P是产生式的有限集合，每个产生式是形如α→β的规则，其中α称为产生式的左部，β称为产生式的右部。S∈V_N，称为开始符号，它至少要在一条产生式中作为左部出现。

2）文法的分类

乔姆斯基把文法分成4种类型，即0型、1型、2型和3型。

0型文法也称为短语文法，其能力相当于图灵机。

（1）1型文法也称为上下文有关文法，这种文法意味着对非终结符的替换必须考虑上下文，并且一般不允许替换成ε串，此文法对应于线性有界自动机。

（2）2型文法是上下文无关文法，对非终结符的替换无须考虑上下文，它对应于下推自动机。

（3）3型文法等价于正规式，因此也称为正规文法或线性文法，它对应于有限状态自动机。

3）句子和语言

设有文法G=(V_N,V_T,P,S)

（1）推导和直接推导。从文法的开始符号S出发，反复使用产生式，将产生式左部的非终结符替换为右部的文法符号序列，直至产生一个终结符的序列时为止。若有产生式α→β∈P，γ，δ∈V*，则γαδ?γβδ称为文法G中的一个直接推导。

（2）直接归约和归约。若文法G中有一个直接推导α?β，则称α是β的一个直接归约；若文法G中有一个推导

，则称γ是δ的一个归约。

（3）句型和句子。若文法G的开始符号为S，那么，从开始符号S能推导出的符号串称为文法的一个句型，即α是文法G的一个句型，当且仅当有以下推导

，α∈V*，若X是文法G的一个句型，且X∈V*_T，则称X是文法G的一个句子。

（4）语言。从文法G的开始符号出发，所能推导出的句子的全体称为文法G产生的语言，记为L(G)。

（5）文法的等价。若文法G，与文法G₂产生的语言相同，即L(G₁)=L(G₂)，则称这两个文法是等价的。

上下文无关文法

上下文无关文法属于乔姆斯基定义的2型文法，被广泛地用于表示各种程序设计语言的语法。对于上下文无关文法G［S］=（VN，VT，P，S），其产生式的形式都是A→β，其中A∈V_N，β∈（V_N∪V_T）^*。

若不加特别说明，下面用大写英文字母A、B、C等表示非终结符，小写英文字母a、b、c等表示终结符号，u、v、w等表示终结符号串，小写希腊字母α、β、γ、δ等表示终结符和非终结符构成的文法符号串。由于一个上下文无关文法的核心部分是其产生式集合，所以文法可以简写为其产生式集合的描述形式。

（1）规范推导（最右推导）。如果在推导的任何一步

其中α、β是句型），都是对α中最右边的非终结符进行替换，则称这种推导为最右推导。最右推导常称为规范推导。同理可定义最左推导。

（2）短语、直接短语和句柄。设αδβ是文法G的一个句型，即

，且满足

和

，则称δ是句型αδβ相对于非终结符A的短语。特别地，如果有

，则称δ是句型αδβ相对于产生式A→δ的直接短语。一个句型的最左直接短语称为该句型的句柄。

文法

描述语言语法结构的形式规则称为文法。文法G是一个四元组，可表示为G=（V_N，V_T，P，S）。其中V_T是一个非空有限集，其每个元素称为一个终结符；V_N是一个非空有限集，其每个元素称为非终结符。V_N∩V_T=Φ，即V_N和V_T不含公共元素。令V=V_N∪V_T，称V为文法G的词汇表，V中的符号称为文法符号，包括终结符和非终结符。S∈V_N，称为开始符号，它至少要在一条产生式中作为左部出现。P是产生式的有限集合，每个产生式形如“α→β”。其中，α称为产生式的左部，α∈V⁺且α中至少含有一个非终结符；β称为产生式的右部，且β∈V^*。若干个产生式α→β₁，α→β₂，…，α→β_n的左部相同时，可简写为α→β₁｜β₂｜…｜β_n，称β_i（1≤i≤n）为α的一个候选式。

（1）文法的分类。乔姆斯基（Chomsky）把文法分成4种类型，即0型、1型、2型和3型。这4类文法之间的差别在于对产生式要施加不同的限制。若文法G=（V_N，V_T，P，S）的每个产生式α→β，均有α∈（V_N∪V_T）^*，α至少含有一个非终结符，且β∈（V_N∪V_T）^*，则称G为0型文法。对0型文法的每条产生式分别施加以下限制，则可得以下文法：

.1型文法：G的任何产生式α→β（S→ε除外）均满足｜α｜≤｜β｜（｜x｜表示x中文法符号的个数）。

.2型文法：G的任何产生式形如A→β，其中A∈V_N，β∈（V_N∪V_T）^*。

.3型文法：G的任何产生式形如A→a或A→aB（或者A→Ba），其中A，B∈V_N，a∈V_T。

0型文法也称为短语文法，其能力相当于图灵机，任何0型语言都是递归可枚举的；反之，递归可枚举集也必定是一个0型语言。1型文法也称为上下文有关文法，它意味着对非终结符的替换必须考虑上下文，并且一般不允许替换成ε串。例如，若αAβ→αγβ是1型文法的产生式，α和β不全为空，则非终结符A只有在左边是α，右边是β的上下文中才能替换成γ。2型文法就是上下文无关文法，其非终结符的替换无需考虑上下文。3型文法等价于正规式，因此也被称为正规文法或线性文法。