适合读者软考中级备考同学阅读时间3.5分钟内容语法树的定义与构造、二义性文法的概念、判断方法、消除二义性、例题1. 什么是语法树语法树Syntax Tree也称推导树或解析树是文法推导过程的图形化表示。它以树形结构展示句子中各个语法成分的层次关系是理解语法分析的重要工具。语法树的特点根节点文法的开始符号。内部节点非终结符。叶节点终结符从左到右排列构成一个句子。每个内部节点的子节点序列对应一个产生式的右部。语法树的作用直观展示句子的语法结构。帮助识别短语、直接短语和句柄。判断文法的二义性。2. 如何构造语法树给定文法GGG和输入串www可以通过最左推导或最右推导逐步构造语法树。每一步替换对应的非终结符就在该非终结符节点下增加子节点。示例文法E → E T | T T → T * F | F F → ( E ) | id输入串id id * id最左推导过程E ⇒ E T ⇒ T T ⇒ F T ⇒ id T ⇒ id T * F ⇒ id F * F ⇒ id id * F ⇒ id id * id根据推导过程画出的语法树文字描述根节点 E左子节点 E右子节点 右子节点 T左子节点 E 继续展开 → T → F → id右子节点 T 展开为 T * F → T 再展开 → F → idF 展开为 id最终语法树的叶节点从左到右为id id * id。3. 文法的二义性二义性定义如果一个文法中存在某个句子它对应两棵不同的语法树或者说有两个不同的最左推导则该文法是二义的。注意二义性是文法的属性不是语言的属性。有些语言可以被二义文法描述也可以被无二义文法描述。为什么需要避免二义性二义性会导致一个程序可能有多种解释编译程序无法确定其含义因此在实际语言设计中通常要求文法无二义。4. 判断二义性的方法判断文法是否二义没有通用算法只能通过观察或证明。常用方法尝试找到一个句子它存在两种不同的最左推导或两棵不同的语法树。常见二义性例子文法E → E E | E * E | id不加括号和优先级限制。句子id id * id有两棵语法树第一棵先做加法后做乘法即(idid)*id第二棵先做乘法后做加法即id(id*id)因此该文法是二义的。5. 消除二义性通常通过改写文法引入优先级和结合性规则来消除二义性。优先级将不同优先级的运算符分层低优先级的产生式放在上层高优先级的放在下层。结合性左结合用左递归右结合用右递归。改造示例原二义文法E → E E | E * E | id改为无二义文法E → E T | T T → T * F | F F → id这个文法规定了加法优先级低于乘法且两者都是左结合。句子idid*id只有一种推导先乘后加。6. 经典例题题目1给定文法S → aS | Sa | a判断该文法是否二义。若二义请说明理由。解句子aaa存在多种推导。例如最左推导1S ⇒ aS ⇒ aaS ⇒ aaa每次用S→aS最后用S→a最左推导2S ⇒ Sa ⇒ Saa ⇒ aaa先用S→Sa再S→a再S→a注意步骤实际上aaa可以由不同顺序的扩展得到不同语法树。该文法是二义的因为同一个句子可以对应不同的语法树先展开左边还是右边。答案二义。题目2下列哪个文法是无二义的A.S → SS | aB.S → aSb | abC.S → aS | bS | εD.S → aS | a解析ASS会导致aaa有多种组合方式如 (aa)a 与 a(aa)→ 二义。B语言{a^n b^n | n≥1}推导唯一 → 无二义。C可生成任意a,b串但ab可由aS→ab和bS→ab不对bS生成b...。实际上ab有多种最左推导检查S ⇒ aS ⇒ ab和S ⇒ bS无法得ab。但aa呢可能也有二义该文法实际上是正则的且每个串的语法树可能唯一但注意S→aS|bS|ε是典型的生成所有串的二义文法例如ab可以先aS再bS也可以先bS再aS不第一个符号决定了路径。实际上该文法是左线性通常无二义。但软考中常认为S→aS|bS|ε是二义的因为比如a可以由S→aS→aε也可以S→aS→a(bS?)不能。我查一下实际上句子a只有一种推导S⇒aS⇒aε。所以可能无二义。但更典型的无二义例子是 B。D语言{a^n | n≥1}推导唯一 → 无二义。答案B 和 D 都是无二义但单选题时通常选最典型的一个如 B 或 D这里软考常见答案是 B题目3判断若一个文法是二义的则它所描述的语言也是二义的。 答案错误二义性是文法的性质语言本身没有二义性之说语言可以被无二义文法描述7. 记忆口诀语法树形根开始内非外终叶成句。二义句有两棵树改写文法来消除。优先级和结合性分层递归不冲突。8. 给备考同学的一句话语法树和二义性是编译原理的基础概念。软考中常以选择题或简答题形式考查给定文法画出某句子的语法树只需理解过程。判断一个文法是否二义找存在多个最左推导的句子。改写二义文法为非二义引入优先级和结合性。记住二义性是文法的缺陷不是语言的缺陷。掌握典型二义文法例子如不加括号的表达式文法考试时就能快速识别。本专栏日更2篇点击头像 → 专栏《软考中级高频考点》订阅#软考中级 #软件设计师 #语法树 #二义性 #编译原理