问题
单项选择题
大多数程序设计语言的语法规则用()描述即可。
A.正规文法
B.上下文无关文法
C.上下文有关文法
D.短语结构文法
答案
参考答案:B
解析:本题考查程序语言基础知识。乔姆斯基文法体系共分为短语结构文法、上下文有关文法、上下文有关文法和正规文法4类。短语结构文法或无限制文法也称为0型文法,其描述能力相当于图灵机,可使用任何的语法描述形式。上下文有关文法也称为1型文法,其描述能力相当于线性有界自动机,语法形式为:xSy->xAy。也就是说,S(非终结符号)推导出A(非终结符号与终结符号的混合串)是和上下文x,y相关的,即S只有在上下文x,y的环境中才能推导出A。上下文无关文法也称为2型文法,其描述能力相当于下推自动机,语法形式如下:S->A,即S可以无条件的推导出A,与上下文无关。正规文法也称为3型文法,等价于正则表达式,其描述能力相当于有穷自动机,语法形式如下:S->Aa,其中最后一个a必须为非终结符。大多数程序语言的语法现象可用上下文无关文法描述。