【软考路上】——编译原理

清疚 2022-08-07 09:52 177阅读 0赞

编译原理在软考中的考点大体上分为以下几点：文法、语法推倒树和算符优先

![Center][]

下面就从这三方面来总结一下。

###        **文法** ###

**基本元素**

首先要了解文法中最基本的两个元素：非终结符和终结符。

非终结符可以理解为还可以拆分的元素，一般用大写字母来表示；终结符当然就可以看做是不可以拆分的元素，终结符不能转换为其他状态，也不能用其他的量来代替，一般用小写字母来表示。

在图中可以看到，一个文法G是由VN,VT,P,S组成的四元组，其中：VN代表非终结符的集合；VT代表终结符的集合；P是一个规则【α→β，α∈（VN∪VT）且α中至少含有一个非终结符，β∈（VN∪VT），】；S是一个符号【S∈VN】。

**文法类型**

0型文法（短语文法）：一个文法G=(VN,VT,P,S)中，如果它的每个产生式α→β都符合α∈（VN∪VT）且α中至少含有一个非终结符，β∈（VN∪VT），那么称G是一个0型文法，如果G0(\{S,A,B\},\{a,b,c\},P,S)的生成式为S→Aa，Aa→B，Ab→abc，B→aba，那么G0是一个0型文法。

1型文法（上下文有关文法）：1型文法在0型文法的基础上多加了一个条件，α的长度必须大于或等于β的长度，上例中G0因为有Aa→B，所以G0(\{S,A,B\},\{a,b,c\},P,S)不符合1型文法。“→”左边符号的数量必须小于等于右边。

2型文法（上下文无关文法）：2型文法在1型文法的基础上多加了一个条件，α必须是非终结符，上例G0中因为有Ab→abc，Ab不是非终结符，所以G0(\{S,A,B\},\{a,b,c\},P,S)不符合2型文法。“→”左边的符号必须是非终结符。

3型文法（正规文法），3型文法在2型文法的基础上多加了一个条件，β中如果包含终结符和非终结符时，非终结符要么都在左侧，要么都在右侧。比如A→aB，B→Bc，那么就不符合3型文法，但如果有A→aB，B→cB，那么就符合3型文法。

从导图中就可以看到，正规式其实就是文法的另一种表达形式，A→xB，B→y就可以推导为正规式A→xy。

### **       语法推倒树** ###

可以直接用一个文法和一张图来理解：

对于文法G=(\{S,A\},\{a,b\},P,S)，有S→aAS|a，A→SbA|SS|ba，把它拆分得到：S→aAS，S→a，A→SbA，A→SS，A→ba，它构造句型aabAa的推倒树为：

![Center 1][]

当然，从一个语法书得到句型，直接从左到右把叶子节点排列就行。

###         **算符优先分析法** ###

**FIRSTVT和LASTVT**

FIRSTVT(A)：对于非终结符A，每个推导式的右侧有A→a…或A→Ca…，则a属于FIRSTVT集；