编译原理第三章 词法分析及词法分析程序

《编译原理第三章 词法分析及词法分析程序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编译原理——前后文无关文法和语言设计扫描器应注意的问题词法分析（3型）语法分析（2型）单词的(Class,Value)二元组表示标识符的长度限制和按“尽可能长”的识别策略超前搜索与回退<,<=,<<,<<=程序3-1输入缓冲注释与空白的删除状态转换图有向图结点表示状态一个初态，箭头指示若干个终态，双圆圈指示边表示转移边上的字符表示转移时应满足的条件字符串的识别0132abcdd右线性文法=>状态转换图设G=(VN,VT,P,S)是一右线性文法,令

2、VN

3、=K，1)则所要构造的状态转换图共有K+1个状态.2)VN中的每个符号分别表示K个

4、状态2.1)G的开始符S为初态状态3)终止状态,用F(VN)标记F是新加(状态）节点右线性文法=>状态转换图aA->aBABA->aAFaA->ε消除ε，重用上述规则AF[other]A若A为起始符（G[A]）A产生式的消除SAXFabc[other]YeSAXFabcYeS->aAA->b

5、bXX->c

6、eYS->aAA->bXX->c

7、ε

8、eY状态图=>右线性文法文法G[0]0->a1S->aA1->d1A->dA1->bA->b0->cS->c0->c2S->cB，2有出弧2->dB->d0132abcdd左线性文法=>状态

9、转换图设G=(VN,VT,P,S)是一左线性文法,令

10、VN

11、=K，1)则所要构造的状态转换图共有K+1个状态.2)VN中的每个符号分别表示K个状态2.1)G的开始符S为终止状态3)起始状态,用R(VN)标记R是新加(状态）节点左线性文法=>状态转换图aA->BaBAA->ε的消除消除ε，重用上述规则RA[other]若A为起始符（G[A]）AA->aRAa不存在这种转换状态图=>左线性文法文法G[3]1->aAa1->1dAAd3->1bSAb2->cBc3->2dSBd0132abcdd状态矩阵状态矩阵Bij=B[Si

12、,aj]=Sk当前状态，扫视字符，语义动作，后续状态程序3-2识别无符号数的状态矩阵语义动作中的返回值ICON、FCON分别为整型数、浮点型数的值；一般说来，无符号数具有形式dmdm-1…d0.d-1…d-nEdd即dmdm-1…d0d-1…d-n*10^(dd-n);程序3-3关于状态无符号数识别矩阵DFA的形式定义DFA:DeterministicFiniteAutomata一个DFAM定义为M=(K,,f,S0,Z)，其中1)K={状态i}2)=字母表，即{输入字符i}3)f:K×->K，f为函数，表示某状态接受某个字

13、母所到达的状态，如：f(p,a)=q,p,qK,a4)S0K，S0为初态5)ZK，且Z，Z为终态集合DFA例子0132abcdd左侧的状态图，在数学上称作DFA，其形式化定义为M=(K,,f,S0,Z)K={0,1,2,3}={a,b,c,d}源状态输入目的状态0a10C21d11b32d3f:S0=0Z={2,3}函数f的推广定义f^f^:K×*->K，表示某状态接受一个字母串（而不是一个字母）所到达的状态，f^的定义依赖于f的定义，f^递归定义如下：1）f^(p,)=p,ifpK，即任意一状态p接受（串长为

14、0）的输入，状态不变2）f^(p,aw)=f^(f(p,a),w),ifpK,a,w*函数f的推广定义f^:例子对于x=adb,x*，那么从状态0可以迁移到的状态p可以这样求出：P=f^(0,adb)=f^(f(0,a),db)=f^(1,db)=f^(f(1,d),b)=f^(1,b)=f^(f(1,b),)=f^(3,)=30132abcdd因为从初态0接受输入字母串adb后，迁移到f^(0,adb)=3Z，所以adb为DFA所识别DFA所识别的语言令M为一DFA，我们：定义L(M)={x

15、f(S0,x)Z,

16、x*}L(M)称为DFAM所识别的语言有定理：L(M)=L(G)，其中M为一DFA，G为一正规文法DFA关键特征状态迁移映射f是入射函数即f(x)f(y)蕴含xy即对任意状态结点p，其出弧上的字母各不相同且不为从状态图角度，如出现下述情况的状态结点，则不是DFA（而是NFA）PQNaaQNPQPQWhy?NFA的形式定义一个NFAM定义为M=(K,,f,S0,Z)，除f外其余成员与DFA相同，f定义为f:K×->(K)，其中(K)为集合K的幂集合，即有

17、(K)

18、=2^

19、K

20、f表示某状态接受某个字母所到达的状态

21、集合，如：f(p,a)={q,m}p,q,mK,a映射f的推广定义f^f^:(K)×*->(K)，表示某状态集合接受一个字母串（而不是一个字母）所到达的状态集合，f^递归定义如下(依赖于f)：f^({p},