编译原理期末复习笔记

Xanadu132025年1月6日大约 2 分钟

第二章：形式文法和形式语言

从文法的开始符号出发进行零步或多于零步的推导得到的文法符号串（S =*=> α）。句型可以既包含终结符号又包含非终结符号。

只包含终结符号的句型称为句子。句子是一种特殊的句型。

文法 G 推导出的所有句子组成的集合，称为语言，记为 L(G)，即：

$L(G)=\{x | S =*> x \text{且} x∈V_T*\}$

一个文法对应一个语言，但一个语言可能由若干个文法产生它，这若干个文法是等价的，称为等价文法。

上下文有关文法，Context Sensitive Grammar

上下文无关文法，Context Free Grammar

要求产生式左边只有1个非终结符号，高级程序设计语言大部分语法结构使用2型文法描述。

例如：

S -> aB | bA
A -> a | aS | bAA
B -> b | bS | aBB

正规文法，Regular Grammar

对于每个产生式，只能是以下两种形式之一：

(1) A -> a 或 A -> aB  // 右线性文法
(2) A -> a 或 A -> Ba  // 左线性文法

一棵子树的所有叶子自左至右排列起来形成一个相对于子树根的短语。

仅有父子两代的一棵子树，它的所有叶子自左至右排列起来所形成的符号串

一个句型的分析树中最左最下那棵只有父子两代的子树的所有叶子的自左至右排列。

最左直接短语称为句柄。