适合读者软考中级备考同学阅读时间3分钟内容文法的基本概念、终结符与非终结符、产生式、推导与归约、例题1. 什么是文法文法是形式语言理论的核心概念用于精确描述程序设计语言的语法规则。一个文法定义了一门语言中哪些符号串是合法的句子。编译程序在语法分析阶段会根据文法判断源程序是否合乎语法规则。软考中常考查文法的基本组成终结符、非终结符、产生式以及文法的分类。2. 文法的形式定义文法GGG是一个四元组G(VT,VN,P,S)G (V_T, V_N, P, S)G(VT​,VN​,P,S)其中VTV_TVT​终结符集合Terminal SymbolsVNV_NVN​非终结符集合Non-terminal SymbolsPPP产生式集合Production RulesSSS开始符号Start SymbolS∈VNS \in V_NS∈VN​3. 终结符Terminal定义文法中不能再被替换的基本符号是语言中实际出现的字符或单词。特点终结符是语言的字母表中的元素它们出现在最终生成的句子中没有产生式可以进一步展开终结符示例在算术表达式文法中,-,*,/,(,), 数字0~9是终结符在程序语言文法中关键字if,else,while运算符,标识符等是终结符通常表示用小写字母、数字或特定符号表示如a,b,,id。4. 非终结符Non-terminal定义可以被进一步展开的语法变量用于表示语法结构。特点非终结符不出现在最终生成的句子中在推导过程中会被终结符序列替代每个非终结符对应一个语法成分如表达式、语句、程序块示例表达式、赋值语句、循环等是非终结符通常用尖括号或大写字母表示如E,T,F,stmt开始符号SSS是一个特殊的非终结符代表整个语法成分的起点。5. 产生式Production Rule定义描述非终结符如何展开的规则形式为α→β\alpha \rightarrow \betaα→β其中α\alphaα左部是至少包含一个非终结符的符号串β\betaβ右部是由终结符和非终结符组成的符号串可以为空串ε\varepsilonε。含义左部的符号可以被右部的符号串替换。示例E → E T E → T T → T * F T → F F → ( E ) F → id这里的箭头→表示“定义为”或“可替换为”。6. 推导与归约推导从开始符号出发反复使用产生式替换非终结符最终得到一个全部由终结符组成的串称为该文法的一个句子。最左推导每次都替换最左边的非终结符。最右推导规范推导每次都替换最右边的非终结符。归约推导的逆过程将终结符串逐步替换为非终结符最终得到开始符号。7. 完整示例文法简单算术表达式S → E E → E T | T T → T * F | F F → ( E ) | idVT{,∗,(,),id}V_T \{, *, (, ), id\}VT​{,∗,(,),id}id代表标识符如变量名VN{S,E,T,F}V_N \{S, E, T, F\}VN​{S,E,T,F}PPP为上述产生式SSS为开始符号推导示例推导句子id id * id的最左推导过程S ⇒ E ⇒ E T ⇒ T T ⇒ F T ⇒ id T ⇒ id T * F ⇒ id F * F ⇒ id id * F ⇒ id id * id8. 文法的分类乔姆斯基体系类型名称产生式形式对应自动机0型短语结构文法α→β\alpha \rightarrow \betaα→β无限制图灵机1型上下文有关文法αAβ→αγβ\alpha A \beta \rightarrow \alpha \gamma \betaαAβ→αγβγ≠ε\gamma \neq \varepsilonγε线性有界自动机2型上下文无关文法A→γA \rightarrow \gammaA→γAAA为单个非终结符下推自动机3型正则文法A→aBA \rightarrow aBA→aB或A→aA \rightarrow aA→a有限自动机软考主要考查2型上下文无关文法因为它足够描述多数程序设计语言的语法结构。9. 经典例题题目1给定文法GGG的产生式如下S → aB | bA A → aS | bAA | a B → bS | aBB | b下列符号串中属于该文法语言的是 。A. aaabbB. abC. ababD. ba解析需要尝试推导。该文法表示一个关于aaa和bbb个数相等的语言。选项 Dba可通过S → bA → ba推导得到A→aA \rightarrow aA→a。其他选项无法推导。答案D题目2在文法中不能出现在最终句子中的符号是 。A. 终结符B. 非终结符C. 运算符D. 标识符答案B题目3判断一个文法的开始符号必须是终结符。 答案错误开始符号是非终结符10. 记忆口诀终结符出现最终句非终结符可继续换。产生式左边变右边推导归约来检验。11. 给备考同学的一句话文法定义是编译原理的基础软考中常以选择题形式考查区分终结符和非终结符看是否能被展开产生式的形式左部至少一个非终结符最左推导/最右推导的过程理解记住终结符是“不能再拆”的单词非终结符是“语法变量”。掌握这个核心区别相关题目即可得分。本专栏日更2篇点击头像 → 专栏《软考中级高频考点》订阅#软考中级 #软件设计师 #文法 #终结符 #非终结符 #产生式 #编译原理