|
|
知识路径: > 嵌入式系统软件基础知识 > 嵌入式系统程序设计 > 嵌入式程序设计语言 > 编译器和解释器的基础知识 > 程序设计语言的翻译基础 >
|
|
被考次数:3次
|
|
被考频率:
中频率
|
|
总体答错率:
46%
|
|
知识难度系数:
|
|
考试要求:
掌握
|
|
相关知识点:12个
|
|
|
|
词法分析过程的本质是对构成源程序的字符串进行分析,是一种对象为字符串的运算。语言中具有独立含义的最小语法单位是符号(单词),如标识符、无符号常数与界限符等。词法分析的任务是把构成源程序的字符串转换成单词符号序列。
|
|
|
|
(1)字母表∑:元素的非空有穷集合。例如,∑={a,b}。
|
|
|
(2)字符:字母表∑中的一个元素。例如,∑上的a或b。
|
|
|
(3)字符串:字母表∑中字符组成的有穷序列。例如,a、ab、aaa都是∑上的字符串。
|
|
|
(4)字符串的长度:字符串中的字符个数。例如,|aba|=3。
|
|
|
(5)空串ε:由0个字符组成的序列。例如,|ε|=0。
|
|
|
(6)连接:字符串S和T的连接是指将串T接续在串S之后,表示为S·T,连接符号“·”可省略。显然,对于字母表∑上的任意字符串S,S·ε=ε·S=S。
|
|
|
|
(8)∑*:指包括空串ε在内的∑上所有字符串的集合。例如,设∑={a,b},∑*={ε,a,b,aa,bb,ab,ba,aaa,…}。
|
|
|
(9)字符串的方幂:把字符串α自身连接n次得到的串,称为字符串α的n次方幂,记为αn。α0=ε,αn=ααn-1=αn-1α(n>0)。
|
|
|
(10)字符串集合的运算:设A、B代表字母表∑上的两个字符串集合。
|
|
|
|
|
.幂:An=A·An-1=An-1·A(n>0),并规定A0={ε}。
|
|
|
|
.闭包*:A*=A0∪A+。显然,∑*=∑0∪∑1∪∑2∪…
|
|
|
|
词法规则可用3型文法(正规文法)或正规表达式描述,它产生的集合是语言基本字符集∑(字母表)上的字符串的一个子集,称为正规集。
|
|
|
对于字母表∑,其上的正规式(正则表达式)及其表示的正规集可以递归定义如下。
|
|
|
(1)ε是一个正规式,它表示集合L(ε)={ε}。
|
|
|
(2)若a是∑上的字符,则a是一个正规式,它所表示的正规集为L(a)={a}。
|
|
|
(3)若正规式r和s分别表示正规集L(r)和L(s),则:
|
|
|
|
|
|
|
仅由有限次地使用上述三个步骤定义的表达式才是∑上的正规式。
|
|
|
运算符“|”“·”“*”分别称为“或”“连接”和“闭包”。在正规式的书写中,连接运算符“·”可省略。运算符的优先级从高到低顺序排列为“*”“·”“|”。
|
|
|
设∑={a,b},在下表中列出了∑上的一些正规式和相应的正规集。
|
|
|
|
|
若两个正规式表示的正规集相同,则认为二者等价。两个等价的正规式U和V记为U=V。例如,b(ab)*=(ba)*b,(a|b)*=(a*b*)*。
|
|
|
|
有限自动机是一种识别装置的抽象概念,它能准确地识别正规集。有限自动机分为两类:确定的有限自动机和不确定的有限自动机。
|
|
|
(1)确定的有限自动机(Deterministic Finite Automata,DFA)。一个确定的有限自动机是个五元组:(S,∑,f,s0,Z),其中:
|
|
|
|
②∑是一个有穷字母表,它的每个元素称为一个输入字符。
|
|
|
③f是S×∑→S上的单值部分映像。f(A,a)=Q表示当前状态为A、输入为a时,将转换到下一状态Q。称Q为A的一个后继状态。
|
|
|
|
⑤Z是非空的终止状态集合,
|
|
|
一个DFA可以用两种直观的方式表示:状态转换图和状态转换矩阵。状态转换图是一个有向图,简称为转换图。DFA中的每个状态对应转换图中的一个结点;DFA中的每个转换函数对应图中的一条有向弧,若转换函数为f(A,a)=Q,则该有向弧从结点A出发,进入结点Q,字符a是弧上的标记。
|
|
|
例如,DFAM1=({s0,s1,s2,s3},{a,b},f,s0,{s3}),其中f为:
|
|
|
f(s0,a)=s1,f(s0,b)=s2,f(s1,a)=s3,f(s1,b)=s2,f(s2,a)=s1,f(s2,b)=s3,f(s3,a)=s3
|
|
|
与DFAM1对应的状态转换图如下图(a)所示,其中,状态s3表示的结点是终态结点。状态转换矩阵可以用一个二维数组M表示,矩阵元素M[A,a]的行下标表示状态,列下标表示输入字符,M[A,a]的值是当前状态为A、输入字符为a时,应转换到的下一状态。与DFAM1对应的状态转换矩阵如下图(b)所示。在转换矩阵中,一般以第一行的行下标对应的状态作为初态,而终态则需要特别指出。
|
|
|
|
|
对于∑中的任何字符串ω,若存在一条从初态结点到某一终止状态结点的路径,且这条路径上所有弧的标记符连接成的字符串等于ω,则称ω可由DFAM识别(接受或读出)。若一个DFAM的初态结点同时又是终态结点,则空字ε可由该DFA识别(或接受)。DFAM所能识别的语言L(M)={ω|ω是从M的初态到终态的路径上的弧上标记所形成的串}。
|
|
|
例如,对于字符串"ababaa",在上图(a)所示的状态转换图中,识别"ababaa"的路径是s0→s1→s2→s1→s2→s1→s3。由于从初态结点s0出发,存在到达终态结点s3的路径,因此该DFA可识别串"ababaa"。而"abab"和"baab"都不能被该DFA接受。对于字符串“abab“,从初态结点s0出发,经过路径s0→s1→s2→s1→s2,当串结束时还没有到达终态结点s3;而对于串"baab",经过路径s0→s2→s1→s3,虽然能到达终态结点s3,但串尚未结束又不存在与下一字符"b"相匹配的状态转换。
|
|
|
(2)不确定的有限自动机(Nondeterministic Finite Automata,NFA)。一个不确定的有限自动机也是一个五元组,它与确定有限自动机的区别如下。
|
|
|
①f是S×∑→2s上的映像。对于S中的一个给定状态及输入符号,返回一个状态的集合。即当前状态的后继状态不一定是唯一确定的。
|
|
|
|
例如,已知有NFAN=({s0,s1,s2,s3},{a,b},f,s0,{s3}),其中f为:
|
|
|
f(s0,a)=s0,f(s0,a)=s1,f(s0,b)=s0,f(s1,b)=s2,f(s2,b)=s3
|
|
|
与NFAM2对应的状态转换图和状态转换矩阵如下图所示。
|
|
|
|
|
显然,DFA是NFA的特例。实际上,对于每个NFAM,都存在一个DFAN,且L(M)=L(N)。
|
|
|
词法分析器的任务是把构成源程序的字符流翻译成单词符号序列。手工构造词法分析器的方法是先用正规式描述语言规定的单词符号,然后构造相应有限自动机的状态转换图,最后依据状态转换图编写词法分析器(程序)。
|
|
|