软考之路——文法_软考文法例子

作者：笔触狂放9 | 2024-04-30 21:35:47

踩

软考文法例子

看了软考视频之后，觉得对文法这一块理解得模模糊糊，傻傻分不清楚，查了查相关资料，下面我们就一起来了解一下吧！

（一）终结符和非终结符

在谈文法之前，我们先来了解两个概念：终结符和非终结符。

终结符：语言中用到的基本元素。就是说，它们能在一个形式语法的推导规则的输入或输出字符串存在，而且它们不能被分解成更小的单位。

非终结符：非终结符是可以被拆分的符号。一个形式文法中必须有一个起始符号。这个起始符号属于非终结符的集合。

我们一般用大写字母来表示非终结符，用小写字母来表示终结符。

（二）四种文法的区别

文法类型

产生式的限制

定义

0型文法

α→β

其中α、β∈(VT∪VN) *，∣α∣≠0

α∈(VT∪VN) * ，且至少含有一个非终结符；

β∈(VT∪VN) *

例如：aA→a，A→a，Aa→a

1型文法

（上下文有关文法）

α→β

其中α、β∈(VT∪VN) *，∣α∣≤∣β∣

首先要满足0型文法，左边α的长度小于等于右边β的长度

例如：A→ab，A→a

2型文法（上下文无关文法）

A→β

其中A∈VN，β∈(VT∪VN) *

每一个A→β都有A是非终结符

例如：A→a，A→ab，AB→BAc

3型文法（正规文法）

A→α|αB(右线性)或A→α|Bα(左线性)

（1）必须符合2型文法

（2）式子右边最多有二个字符，而且如果有二个字符必须是一个终结符和一个非终结符；如果只有一个字符，那么必须是终结符

（3）式子右边的格式要一致：必须全为aB或者全为Ab

对于3型文法，当时看视频没有看太懂。在这里，再讲解一下3型文法的定义。

3型文法，也叫正规文法，它是在2型文法的基础上满足：A→α|αB(右线性)或A→α|Bα(左线性)

例如：右线性：A→a,A→aB,B→a,B→cB(必须全为aB形式)

例子：A→ab,A→aB,B→a,B→cB中的A→ab不符合3型文法的定义,如果把后面的ab,改成aB(即“一个非终结符＋一个终结符”)就对了。

左线性：A→a,A→Ba,B→a,B→Bc(必须全为Ab形式）
例子：A→a,A→Ba,B→a,B→cB中如果把B→cB改为B→Bc的形式就对了

左线性和右线性两套规则不能同时出现在一个语法中，必须完全满足其中一个，才能算3型算法。

（三）四种文法的联系

一张图胜过千言万语。

理解不当，还请多多指教！！

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/515337