文法和语言的形式描述-软考在线

文法和语言的形式描述


知识路径： > 计算机系统基础知识 > 计算机软件知识 > 程序设计语言和语言处理程序知识 > 汇编、编译、解释系统的基础知识和基本工作原理 > 编译程序的基本原理 >
被考次数：6次被考频率：中频率总体答错率：42% 知识难度系数：	由软考在线用户真实做题大数据统计生成
相关知识点：6个

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₂)，则称这两个文法是等价的。

本知识点历年真题：

隶属试卷

题号/题型

题干

难度系数/错误率

   2018年上半年
   软件设计师
   上午试卷综合知识

第50题
选择题

简单算术表达式的结构可以用下面的上下文无关文法进行描述(E为开始符号)，（50）是符合该文法的句子。
    E→T|E+T
    T→F|T*F
    F→-F|N
&nb..

51%

   2016年下半年
   软件设计师
   上午试卷综合知识

第49题
选择题

乔姆斯基（Chomsky）将文法分为4种类型，程序设计语言的大多数语法现象可用其中的（49）描述。

45%

>> 更多本知识点历年真题


	相关知识点：
	编译程序的基本原理编译过程概述词法分析目标代码生成语法分析中间代码优化

	软考在线指南
	优惠劵及余额
	在线支付
	修改密码
	下载及使用
	购买流程
	取消订单

	联系我们
	关于我们
	联系我们
	商务合作

旗下网站群

高级资格科目
信息系统项目管理师	系统分析师
系统架构设计师	网络规划设计师
系统规划与管理师
初级资格科目
程序员	网络管理员
信息处理技术员	信息系统运行管理员

中级资格科目
系统集成项目管理工程师	网络工程师
软件设计师	信息系统监理师
信息系统管理工程师	数据库系统工程师
多媒体应用设计师	软件评测师
嵌入式系统设计师	电子商务设计师
信息安全工程师

本网站所有产品设计（包括造型，颜色，图案，观感，文字，产品，内容），功能及其展示形式，均已受版权或产权保护。
任何公司及个人不得以任何方式复制部分或全部，违者将依法追究责任，特此声明。
本站部分内容来自互联网或由会员上传，版权归原作者所有。如有问题，请及时联系我们。

工作时间：9:00-20:00

客服

商务合作

客服邮箱service@rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5 |