编译原理第3章+词法必威体育精装版.ppt

* * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 实际上，有穷自动机是1953年由Huffman提出一种数学模型，主要用于研究时序电路、生物网络神经等。如，电梯控制就是有穷自动机的典型应用。另外，我们在人工智能、形式语言理论研究也要应用有穷自动机。 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * 其中０为初态，２为终态（双圆圈表示）。 这个转换图识别（接受）标识符过程是： （1）从初态０开始，若在状态０之下输入字符是一个字母则转入状态１。 （2）在状态１之下，若下一个输入字符为字母或数字，则读进它，并重新 进入状态1。 （3） 重复（2），直到状态１发现输入字符不再是字母或数字时就进入 状态２。状２是终态，它意味着到此已识别出一个标识符，识别 过程宣告终止。 终态结上打个星号，表示多读进一个不属于标识符的字符， 应把它退还给输入串。 （4） 如果在开始状态0下，输入字符不是字母，则意味着识别不出标识符 按同样的方法，同学们可以考虑一下整数的识别状态转换图及识别过程 * * 由该文法所确定的语言为 Ｌ［Ｇ］＝｛０１，１０}+ * * * * * * * * * * * * * * * * * * * * * 四、LEX的目标程序——词法分析程序 词法分析程序主要由两部分组成：一张转换矩阵表和一个控制程序。尽管程序设计语言不同，但是总控程序却是一样的。 * 作业讲解 P39 15. 设文法G规则为： S::=AB B::=a|Sb A::=Aa|bB 对下列句型给出推导语法树，并求出其句型短语，简单短语和句柄。 (1)baSb (2)baabaab (3)bBABb * 作业讲解 P.41：习题24.下面文法那些是短语结构文法，上下文有关文法，上下文无关文法，及正规文法？ 1.S::=aB B::= cB B::=b C::=c 2.S::=aB B::=bc C::=c C::=ε 3.S::=aAb aA::=aB aA::=aaA B::=b A::=a 4.S::=aCd aC::=B aC::=aaA B::=b 5.S::=AB A::=a B::=bC B::=b C::=c 6. S::=AB A::=a B::=bC C::=c C::=ε 7. S::=aA S::=ε A::=aA A::=aB A::=a B::=b 8. S::=aA S::= ε A::=bAb A::=a * 正规文法 1、 7 上下文无关文法 2、 5、 6、 8 上下文有关文法 3 短语结构文法 4 * P.41：习题25设有文法G[S}: S::=AB A::=bB | bC | ba B::=Sb |ba |a C::=Bb | b 试分别用自顶向下和自底向上的方法，分析符号串bbbabba是否属于语言L(G) * * * 最右推导： S=AB=Aba =bBba = bSbba=bABbba=bAabba =bbCabba=bbbabba * 步骤 符号栈 输入符号 动作 1 # bbbabba# #入栈 2 #b bbabba# b入栈 3 #bb babba# b入栈 4 #bbb abba# b入栈 5 #bbC abba# 用C?b归约 6 #bA abba# 用A?bC归约 7 #bAa bba# a入栈 8 #bAB bba# 用B?a归约 9 #bS bba# 用S?AB归约