编译原理（3）总结

上下文无关文法

定义:
??上下文无关文法G是一个四元组，\(G=(V_T,V_N,S,P)\)，其中
??\(V_T\)：终结符（Terminal）非空集合
??\(V_N\)：非终结（Nonterminal）非空集合，且\(V_T \cap V_N=\oslash\)
??S：文法的开始符号，\(S\subset V_N\)
??P：产生式有限集合，每个产生式形式为

??且文法开始符号S必须在某个产生式的左部出现一次。

巴科斯范式（BNF）

“→”用“::=”表示，小写字母为终结符，大写字母为非终结符。
约定：

可缩写为

其中，“|”读成“或”，称\(\alpha_i\)为P的一个候选式，表示一个文法时，通常只给出一个开始符号和产生式

文法生成语言

直接推导

定义：
?? 称\(\alpha A \beta\)直接推出\(\alpha \gamma \beta\)，即

??仅当\(A \to \gamma\)是一个产生式，且\(\alpha,\beta \in(V_T \cup V_N)^*\)。
??如果\(\alpha_1 \implies \alpha_2 \implies ... \implies \alpha_n\)，则称这个序列是从\(\alpha_1\)到\(\alpha_n\)的一个推导。若存在一个从\(\alpha_1\)到\(\alpha_n\)的推导，则称\(\alpha_1\)可以推导出\(\alpha_n\)。
??\(\alpha_1 \overset{*}{\implies} \alpha_n\)，从\(\alpha_1\)出发，经过\({\color{red}0}\)步或者若干步推出\(\alpha_n\)。
??\(\alpha_1 \overset{+}{\implies} \alpha_n\)，从\(\alpha_1\)出发，经过\({\color{red}1}\)步或者若干步推出\(\alpha_n\)。
??\(\alpha \overset{*}{\implies} \beta \iff \alpha = \beta 或 \alpha \overset{+}{\implies}\beta\)

句型

定义
??假定G是一个文法，S是它的开始符号，如果

??则称\(\alpha\)是一个\(\color{red}{句型}\)。

句子

定义：仅含终结符的句型是一个\(\alpha\)是一个\(\color{red}{句子}\)。

语言

定义：文法G所产生的句子的全体是一个\(\color{red}{语言}\)，记为：\(\color{red}L(G)\)。

??概述为把语言定义为句子的全体，也就是说，你如果掌握了一个语言所有的句子，就等于你掌握了这一门语言！

编译原理（3）总结

原文：https://www.cnblogs.com/hkfyf/p/14094571.html