编译原理学习笔记（二）:形式语言基础

形式语言基础

如不了解编译原理的基本概念，可以参考此文：
[编译原理的基本概念：] (https://blog.****.net/m0_49263811/article/details/108099365?utm_source=app)

简介：

计算机处理语言，首先应该考虑语言的形式化、规范化，使其具有可计算性和可操作性，这就是形式语言理论研究的问题。
形式语言由Chomsky创立，通常语言研究至少涉三个方面：语法、语义和语用；

图片来源于网络，侵删。
1.1 形式语言是符号串的集合

符号串的连接、或、方幂和闭包：

1.2 形式语言是由文法定义的

1.4 形式语言的分类
（1）0型语言：又称无限制文法！
产生式形式：α->β

（2）1型文法：又称上下文有关文法！
产生式形式：αAβ->αuβ

（3）2型语言：又称上下文无关法！
产生式形式：A->β

（4）3型语言：又称正规文法！
产生式形式：A->aB或A->a =>右线性文法
A->Ba或A->a =>左线性文法

1.3 各种语法成分的定义


实用中最常见的两种运算：
最左推导——每次推导皆最左非终结符优先。
最左规约——每次规约皆最左可规约串优先。
注意：最左规约是最右推导的逆过程！

1.4 文法的等价变换

文法变换方法
在实际工作中，人们总是希望定义一种语言尽可能简单，另外有些常用的语法分析技术对文法提出一定的要求和限制，所以有时要对文法进行变换。

主要介绍两类变换：
I 删除无用的产生式（文法的化简）
II 删除є产生式。