当前位置:网站首页>编译原理之文法
编译原理之文法
2022-08-09 21:43:00 【全栈程序员站长】
大家好,又见面了,我是你们的朋友全栈君。
文法(Grammar):
G={VT,VN,S,P}
VT是一个非空有限的符号集合,它的每个元素称为终结符号(Terminal)
VN是一个非空有限的符号集合,它的每个元素称为非终结符号(Non-Terminal)
S∈VN,称为文法G的开始符号
P是一个非空有限集合,它的元素称为产生式。
VT∩VN=∅
产生式,其形式为α→β,α称为产生式的左部,β称为产生式的右部,符号“→”表示“定义为”,并且α、β∈(VT∪VN) *,α≠ε,即α、β是由终结符和非终结符组成的符号串。
开始符S必须至少在某一产生式的左部出现一次。
另外可以对形式α→β,α→γ的产生式缩写为α→β|γ,以方便书写。
解释:
(VT∪VN) *:也就是VT∪VN的Kleene闭包
α≠ε:α不等于空符号串
用小写字母代表终结符,如:abc……,不能被拆分
用大写字母代表非终结符,如:ASBX……,可以被拆分
著名语言学家NoamChomsky(乔姆斯基)根据对产生式所施加的限制的不同,把文法分成四种类型,即0型、1型、2型和3型。
文法类型 | 产生式的限制 | 文法产生的语言 |
---|---|---|
0型文法 | α→β 其中α、β∈(VT∪VN) *,∣α∣≠0 | 0型语言 |
1型文法 | α→β 其中α、β∈(VT∪VN) *,∣α∣≤∣β∣ | 1型语言,即上下文有关语言 |
2型文法 | A→β 其中A∈VN,β∈(VT∪VN) * | 2型语言,即上下文无关语言 |
3型文法 | A→α|αB(右线性)或A→α|Bα(左线性) 其中,A,B∈VN,α∈VT∪{ ε} | 3型语言,即正规语言, 又分为左线性语言和右线性语言 |
0型文法:α∈(VT∪VN) * 且至少含有一个非终结符,而β∈(VT∪VN) *
例:A→a,Aa→a,aA→a(左边至少有一个大写字母)
1型文法:有一特例:α→ε也满足1型文法。
例:A→a,A→ab,Aa→BAc(左边至少有一个大写字母,且左边的长度小于等于右边的长度)
2型文法:每一个A→β都有A是非终结符
例:A→a,A→ab,AB→BAc(在1型文法的前提下,左边必须都是大写字母)
3型文法:如有:A→a,A→aB,B→a,B→cB,则符合3型文法的要求。
但如果推导为:A→ab,A→aB,B→a,B→cB或推导为:A→a,A→Ba,B→a,B→cB则不符合3型方法的要求了。
例子:A→ab,A→aB,B→a,B→cB中的A→ab不符合3型文法的定义,如果把后面的ab,改成aB(即“一个非终结符+一个终结符”)就对了。
例子:A→a,A→Ba,B→a,B→cB中如果把B→cB改为B→Bc的形式就对了,因为A→α|αB(右线性)和A→α|Bα(左线性)两套规则不能同时出现在一个语法中,只能完全满足其中的一个,才能算3型文法。
如果所有的终端结点都是与终结符关联的,每棵推导树的终端结点自左至右所构成的字符串应该是文法G的一个句型,则该字符串是文法G的一个句子,此时该推导树是完全推导树。
如:文法G=({a,b},{S,A},S,P),其中:S→aAS|a,A→SbA|SS|ba,句型aabAa相对应的构造树。
解释:
文法G={VT,VN,S,P},即VT={a,b},VN={S,A}
S→aAS|a,即S→aAS,S→a
A→SbA|SS|ba,即A→SbA,A→SS,A→ba
发布者:全栈程序员栈长,转载请注明出处:https://javaforall.cn/105720.html原文链接:https://javaforall.cn
边栏推荐
- 2021(ICPC)亚洲区域赛昆明站(CGHIJLM)
- 如何让您的公司内容满足 GDPR 合规性
- Cookie, session, token
- Use zeros(), ones(), fill() methods to generate data in TF
- AI识万物:从0搭建和部署手语识别系统
- 宝塔实测-搭建LightPicture开源图床系统
- [corctf 2022] 部分
- Install Mysql8.0 on windos, and solve the problem of re-login exception ERROR 1045 (28000)
- 【Efficient Tools】Remote Control Software ToDesk (Favorites)
- 基于Docker构建MySQL主从复制数据库
猜你喜欢
角度和弧度的相互换算
[corctf 2022] section
必看设计干货|易知微设计师是怎么做标准可视化设计服务的?
小黑leetcode清爽雨天之旅,刚吃完宇飞牛肉面、麻辣烫和啤酒:112. 路径总和
万字总结:分布式系统的38个知识点
PMP每日一练 | 考试不迷路-8.9(包含敏捷+多选)
DSPE-PEG-PDP, DSPE-PEG-OPSS, phospholipid-polyethylene glycol-mercaptopyridine reduce the immunogenicity of peptides
Several ways to draw timeline diagrams
数独 | 回溯-7
Word文档怎么输入无穷大符号∞
随机推荐
SQLi-LABS Page-2 (Adv Injections)
Tensorflow模型整体构建流程
NIO Cup 2022 Nioke Summer Multi-School Training Camp 7 CFGJ
Interpretation of the paper (DropEdge) "DropEdge: Towards Deep Graph Convolutional Networks on Node Classification"
Use zeros(), ones(), fill() methods to generate data in TF
Unity_物体自转
Problems with compiling SIP with QGIS
编程语言中,取余和取模的区别
POWER SOURCE ETA埃塔电源维修FHG24SX-U概述
编程时请选择正确的输入法,严格区分中英文
自监督学习 —— MoCo v2
Tensorflow中placeholder函数的用法
什么是IDE(集成开发环境)?
筑牢安全防线 鹤壁经济技术开发区开展安全生产培训
How to Make Your Company Content GDPR Compliant
Leetcode 93 IP addresses
[Implementation of the interface for adding, deleting, checking, and modifying a double-linked list]
Jmeter 使用正则表达式提取器将返回值全部保存到一个文件中
AI识万物:从0搭建和部署手语识别系统
Daily practice of PMP | Do not get lost in the exam -8.8 (including agility + multiple choice)