原文地址

第一节 基本概念

形式文法（Formal grammar）
形式语言(Formal language)是：某个字母表上，一些有限长字串的集合，而形式文法是描述这个集合的一种方法。形式文法之所以这样命名，是因为它与人类自然语言中的文法相似的缘故。

一个形式文法G是下述元素构成的一个四元组（N, Σ, P, S）：

• “非终结符号”集合N。
• “终结符号”集合Σ，Σ与N无交。
• 取如下形式的一组“产生式规则” P，(Σ ∪ N)中的字符串→ (Σ ∪ N) 中的字符串（这里的*是克莱尼星号），并且产生式左侧的字符串中必须至少包括一个非终结符号。
• “起始符号”S，S属于N。

一个由形式文法G = (N, Σ, P, S)产生的语言是所有如下形式的字符串集合，这些字符串全部由“终结符号”集Σ中符号构成，并且可以从“初始符号”S出发，不断应用P中的“产生式规则”而得到。

产生式（production）
语法单元或单元组可以称之为符号（symbol），由更小的单元连接在一起构成的单元组称之为非终结符（nonterminal symbols），无法被分割的符号称之为终结符（terminal symbols）。
产生式的左面至少有一个非终结符。

symbol symbol...... symbol → symbol symbol...... symbol

上下文无关文法 （Languages and Context-Free Grammars）
上下文无关文法要求产生式左侧只能包含一个符号，并且该符号为非终结符号。