文章目录形式语言与文法基础笔记一、核心概念总览二、终结符与非终结符1. 终结符Terminal2. 非终结符Non-terminal3. 对比总结三、产生式Production1. 定义2. 基本形式3. 多重选择4. ε空串四、文法Grammar1. 定义2. 文法的四元组表示3. 文法的本质五、推导Derivation1. 定义2. 符号表示3. 推导示例六、句型与句子1. 句型Sentential Form2. 句子Sentence3. 对比总结七、语言Language1. 定义2. 示例八、递归与无限语言1. 递归规则2. 递归的意义3. 推导示例九、快速判断清单十、常见易错点形式语言与文法基础笔记一、核心概念总览形式语言与文法是编译原理的基石主要研究什么样的字符串是合法的以及如何用规则生成这些字符串。核心概念包括文法、终结符、非终结符、产生式、推导、句型、句子和语言。二、终结符与非终结符1. 终结符Terminal定义文法中不可再被替换的基本符号是最终输出字符串的组成元素。表示习惯通常用小写字母a, b, c或具体单词if, while, 珍珠, 椰果表示。特点推导到终结符时该位置就定型了不会再变化。2. 非终结符Non-terminal定义文法中必须被替换的中间符号代表某种语法结构或制作步骤。表示习惯通常用大写字母S, A, B或有意义的名称表达式, 语句表示。特点推导过程中非终结符必须最终全部被替换为终结符或 ε否则推导未完成。3. 对比总结对比项终结符非终结符能否再替换不能必须被替换角色最终输出的原料中间过程的步骤/占位符常见符号小写字母 a, b大写字母 S, A, B三、产生式Production1. 定义产生式是文法中的规则用箭头→表示可以替换为。2. 基本形式非终结符 → 替换内容3. 多重选择用竖线|分隔多个选项表示或的关系A → aA | ε含义A 可以替换为aA也可以替换为ε空串。4. ε空串ε 既不是终结符也不是非终结符它是一个特殊符号表示什么都没有。当某条规则包含 ε 选项时意味着该非终结符是可选的可以直接消失。四、文法Grammar1. 定义文法是一套产生式规则的集合它定义了某种语言中所有合法字符串的生成方式。2. 文法的四元组表示文法 G 通常表示为 G (V, T, P, S)V非终结符集合T终结符集合P产生式规则集合S开始符号起始非终结符推导总是从 S 出发3. 文法的本质用有限的规则描述可能无限的字符串集合。五、推导Derivation1. 定义推导是从开始符号 S 出发反复使用产生式规则将非终结符逐步替换的过程。2. 符号表示⇒表示一步推导⇒*表示零步或多步推导3. 推导示例已知文法S → ABA A → aA | ε B → bB | ε一条完整的推导链S ⇒ ABA ⇒ aABA ⇒ aAA ⇒ aA ⇒ a每一步都选择一个非终结符应用一条对应的产生式规则进行替换。六、句型与句子1. 句型Sentential Form定义从 S 出发经过任意步推导包括 0 步得到的符号串。特点可能包含非终结符也可能不包含。举例在上述推导中ABA、aABA、aAA、aA都是句型。2. 句子Sentence定义从 S 出发推导得到的、只包含终结符的符号串。特点是推导的最终成品不含任何非终结符。举例在上述推导中a是一个句子。3. 对比总结对比项句型句子是否含非终结符可能含有一定不含是否可继续推导含非终结符时可继续不可继续本质推导过程中的任意状态推导的最终结果关键判断一个串是句型还是句子看它是否含有非终结符。含有非终结符的是句型全是终结符的是句子。七、语言Language1. 定义一个文法 G 所生成的语言 L(G)是该文法能推导出的所有句子的集合。2. 示例对于文法S → AB A → aA | ε B → bB | ε其生成的语言为任意数量的 a 后面跟任意数量的 b包括空串。即{ε, a, b, aa, ab, bb, aaa, aab, abb, bbb, …}注意像 “ba”、“abab” 这种 b 出现在 a 前面或 a、b 交替出现的串该文法无法生成。八、递归与无限语言1. 递归规则当一条产生式的右侧包含左侧相同的非终结符时就形成了递归A → aA | ε右侧的aA中又包含了 A 本身。2. 递归的意义递归使得有限的规则可以生成无限的句子。每次应用递归规则字符串就增长一次选择 ε 则终止增长。计算机语言中的循环结构、嵌套结构如括号匹配、if 嵌套都依赖递归实现。3. 推导示例A ⇒ aA ⇒ aaA ⇒ aaaA ⇒ aaaε aaa通过递归A 可以生成任意长度的 a 串。九、快速判断清单遇到题目时按以下步骤思考识别符号类型大写 非终结符小写 终结符理解产生式→是替换为|是或ε是空/可选执行推导从 S 出发每步选一个非终结符用对应规则替换判断结果含非终结符 → 句型全是终结符 → 句子总结语言把所有可能的句子归纳成一条规律十、常见易错点ε 不是终结符它是特殊符号表示空串不属于终结符也不属于非终结符。句型不一定是句子只有不含非终结符的句型才是句子。句子一定是句型句子是句型的一种特殊情况推导完成的句型。推导顺序不影响结果左推导和右推导只是选择非终结符的顺序不同最终生成的语言相同。递归 ≠ 无限循环递归规则总有 ε 选项或其他终止条件来结束推导否则该文法无法生成任何句子。