上一篇链接：每天两小时学习编译原理——一个学期的第四天，希望能坚持长久✨
下一篇链接：每天两小时学习编译原理——一个学期的第六天，希望能坚持长久✨

程序语言的语法描述

文法

可参考数书上26页。

几个概念

接下来，我们队文法进行形式化的描述，那我们首先引入几个概念，之后利用这些概念使得对文法的描述变得加准确。

接下来，我们就可以定义一个子集之间的运算，这个运算就是连接：

直观上说，两个子集之间的连接就是把两个集合中的字符串进行拼接，得到的所有可能的字符串所构成的结果。当然，我们的子集是有运算顺序的,所以UV≠VU。
小例子：

还有一些定义：

那我们的$V^{\ast }$其实也叫Kleene闭包，但是我更愿意称之为“克林闭包”,那有$V^0$光头嘛，就是克林的啦；是个"+"，那就是正则闭包。那两者的区别直接在图中显示的很清楚，有无空子而已。

还是之前的例子：简单例子简单理解

上下文无关文法

有了上面的一些基本概念，我们接下来可以将自然语言的文法例子进行更为详细的解释：
终结符是不允许再分解和定义的单位，如‘He’，‘me’，‘a’，‘book’，‘gave’这些单个单词。
而非终结符是可再分解定义的，如句法单位中的“谓语”，“主语”，“间宾”，“直宾”等。
那这里，我们的非终结符是可以有非终结符与终结符构成。如：句法单位可以由更小的句法单位构成；在程序语言中，有“表达式”，“语句”，“程序”等非终结符。
那S是一个特殊的终结符，它代表所定义的语言最终所感兴趣的语法单位。如：英语中的<句子>这个语法单位；对于描述程序语言的文法来说，<程序>这个句法单位是文法的开始符号。
最后也是最重要的产生式集合P:那其中我们的->的含义(读成)是“定义为”。
详细来看一下这个式子。
以上的“句法”可以理解为“语法”。

我们的P是一个非终结符，而α是一个由终结符与非终结符组成的克林闭包。左边的P是被定义的句法单位，右边的α是构成这种句法单位的一种组合。

那我们再回头看：

那我们就可以将上下文无关文法G所要表达的含义就是：上下文无关文法其实就是定义了一个非终结符：产生式P。
那为了让文法有意义，所以我们加上一句：开始符S至少必须在某个产生式的左边出现一次。
下面我们举个栗子：
先看第一个产生式：E->i
从左往右理解：一个表达式可以由一个标识符表达，
从右往左理解：单独的一个标识符可以构成一个表达式。
第二条：E->E+E
从左往右理解：一个表达式可以由两个子表达式通过加号连接而成。
从右往左理解：两个表达式通过加号连接出来的串也是一个表达式。
第三条：E->E*E与上述加号同理
第四条：听得有点懵，叫E可以有一个括号和其本身构成。
那除了上面的表达产生式的语法规则，还有一种称之为：BNF,大家可自行了解。

接着往下，为了更方便的描述文法，我们还可以做一些简化的约定，
我们要理解一个点：大写字母为非终结符，小写字母或符号为终结符。

文法生成语言

我们首先要清楚一个概念：推导

我们举一个之前的栗子：

还有一些概念：

那从S开始，我们经过0步或n步推出α的过程称这是一个α的一个句型。
栗子：

文法与语言

那以A->Ab这样的定义进行推导的文法中，这种定义称之为递归定义，每次使用递归候选进行替换时，都会导致句型变长，这样，我们就可以产生结构相似，长度递增的句子。
再来一道题：

那我们将上面这和例子稍作修改就变成了：

那我们要是想要去针对某一个语言去编写此语言的文法，我们首先要对语言分析，找出其模式的特点，然后利用递推或递归的方式找出构成句子的模式，从而得到文法规则。

那我们再模仿上例去看一道题：

还是使用了递归的思维。

推导与语法树

下面我们用最左推导来表示语法树：
那我们用最右推导出的语法树其实和上面的结构式是一致的，只是语法树的生长顺序不同。
那最左推导出的语法树是：从上往下，从左往右生长。
那最右推导出的语法树是：从上往下，从右往左生长。

我们要注意两点：

1. 父子结点可以同名
2. 语法树并不反映结点产生的先后顺序，只反映了语法结构的定义或者说是构成关系。
   

语法树与二义性

那语法树这种形式的出现也是为了我们更好的描述一个句子语法结构的层次。
那二义性是什么意思？

我们要明白一点语言的二义性比文法的二义性更强一点。即如果一个语言是二义的，那这个语言中就不会存在非二义性的文法。
那举个栗子：
我们在这个句子中包含两个意思，该图为其中的一个意思，那翻译过来是John在船上看到了Mary。那这里的状语就是修饰saw的，在船上看到的。
那还有个意思为：
这个状语是修饰Mary的，John看见Mary在船上。
那这其实就说明了英语的文法是二义的，即英语是一门二义性的语言。那中文句子就不用举了，中文更复杂。

二义性：

无二义文法推导过程：

那就有一个问题:怎么判断一个文法是否是二义的？

形式语言鸟瞰

这个小结的内容了解即可，感兴趣的请自行深入。
左线性文法与右线性文法其实没有差别
这个能力的比较与范式类似。
这里着重介绍1型和2型

总结

那今天就到这里了。

那若本篇内容对您有所帮助，请三连点赞，关注，收藏支持下。
别问，问就是
创作不易，白嫖很爽，但是求各位手下留情。
如果本篇博客有任何错误或者疏漏，请批评斧正，感激不尽 ！

最后

以上就是默默面包为你收集整理的每天两小时学习编译原理——一个学期的第五天，希望能坚持长久✨程序语言的语法描述的全部内容，希望文章能够帮你解决每天两小时学习编译原理——一个学期的第五天，希望能坚持长久✨程序语言的语法描述所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。