题目

给定文法:S∷=a|∧|(T)T∷=T,S|S(1)改写这个文法,消除左递归。(2)改写后的文法是否是LL(1)文法?若是,构造它的LL(1)分析表。(3)写出该文法所描述的语言是什么?

给定文法:S∷=a|∧|(T)T∷=T,S|S(1)改写这个文法,消除左递归。(2)改写后的文法是否是LL(1)文法?若是,构造它的LL(1)分析表。(3)写出该文法所描述的语言是什么?

题目解答

答案

解:(1)改写后的文法为:S∷=a | ∧ | (T)T∷=ST’T’∷=,ST’ | ε(2)①构造FIRST集FIRST(S)= FIRST(T)={ a, ∧, ( }FIRST(T’)={ , , ε }②构造FOLLOW集FOLLOW(S)={ #, , , ) }FOLLOW(T)= FOLLOW(T’)={)}③构造LL(1)分析表FIRST(a)={a}FIRST(∧)={∧}FIRST((T))={(}FIRST(ST’)={ a, ∧, ( }FIRST(,ST’)={, }a∧(),#SS→aS→∧S→(T)TT→ST’T→ST’T→ST’T’T’→εT’→,ST’从分析表可以看出,不存在冲突,所以改写后的文法是LL(1)文法。(3)描述的语言是以a或者~为元组成分的n元组,例如(a, ~, a, ~, a)

解析

考查要点：本题主要考查文法的左递归消除、LL(1)文法的判断及分析表的构造，以及文法语言的描述。

解题核心思路：

  1. 消除左递归：通过改写文法，将直接左递归转换为间接左递归，消除冲突。
  2. 判断LL(1)文法：通过计算FIRST和FOLLOW集合，构造分析表，检查是否存在冲突。
  3. 语言描述：根据文法规则推导生成的符号序列特征。

破题关键点：

  • 左递归消除的关键是将形如A∷=Aα | β的规则改写为A∷=βA'，A'∷=αA' | ε。
  • LL(1)判断需确保分析表中每个单元无多重定义。
  • 语言特征需结合文法的递归结构和符号组合方式。

(1) 消除左递归

原文法中，T∷=T,S | S存在直接左递归。改写步骤如下：

  1. 提取公共部分：将T的定义拆分为T∷=ST'。
  2. 处理剩余部分：将原规则T,S中的T替换为ST'，得到T'∷=,ST' | ε。

改写后的文法：

S∷=a | ∧ | (T)
T∷=ST'
T'∷=,ST' | ε

(2) 判断LL(1)文法

构造FIRST集

  • FIRST(S)：直接推导出的符号为a、∧、(T)，故FIRST(S) = {a, ∧, (}。
  • FIRST(T)：T = ST'，FIRST(T) = FIRST(S) = {a, ∧, (}。
  • FIRST(T')：T'可推导出,ST'或ε，故FIRST(T') = {, , ε}。

构造FOLLOW集

  • FOLLOW(S)：S出现在(T)中，且T后可能接), ,或结束符#，故FOLLOW(S) = {#, , ), }。
  • FOLLOW(T)：T出现在(T)中，后接)，故FOLLOW(T) = {)} }。
  • FOLLOW(T')：T'与T同上下文，故FOLLOW(T') = {)} }。

构造LL(1)分析表

根据FIRST和FOLLOW集，分析表如下：

  • S的产生式：根据输入符号选择对应规则。
  • T和T'的产生式：根据当前符号匹配FIRST集。

结论：分析表无冲突，改写后的文法是LL(1)文法。

(3) 语言描述

文法生成的字符串由a或∧组成，可能嵌套或逗号分隔。例如：(a, ∧, (a, ∨))。