首页 > 知识点讲解
       词法分析
知识路径： > 嵌入式系统软件基础知识 > 嵌入式系统程序设计 > 嵌入式程序设计语言 > 编译器和解释器的基础知识 > 程序设计语言的翻译基础 > 
被考次数：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。
               （7）空集：用符号Φ表示。
               （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代表字母表∑上的两个字符串集合。
               .或（合并）：A∪B={α|α∈A或α∈B｝。
               .积（连接）：AB=｛αβ|α∈A且β∈B｝。
               .幂：An=A·An-1=An-1·A（n>0），并规定A0={ε}。
               .正则闭包+：A+=A1∪A2∪A3∪…
               .闭包*：A*=A0∪A+。显然，∑*=∑0∪∑1∪∑2∪…
               正规表达式和正规集
               词法规则可用3型文法（正规文法）或正规表达式描述，它产生的集合是语言基本字符集∑（字母表）上的字符串的一个子集，称为正规集。
               对于字母表∑，其上的正规式（正则表达式）及其表示的正规集可以递归定义如下。
               （1）ε是一个正规式，它表示集合L（ε）={ε}。
               （2）若a是∑上的字符，则a是一个正规式，它所表示的正规集为L（a）={a}。
               （3）若正规式r和s分别表示正规集L（r）和L（s），则：
               ①r|s是正规式，表示集合L（r）∪L（s）。
               ②r·s是正规式，表示集合L（r）L（s）。
               ③r*是正规式，表示集合（L（r））*。
               ④（r）是正规式，表示集合L（r）。
               仅由有限次地使用上述三个步骤定义的表达式才是∑上的正规式。
               运算符“|”“·”“*”分别称为“或”“连接”和“闭包”。在正规式的书写中，连接运算符“·”可省略。运算符的优先级从高到低顺序排列为“*”“·”“|”。
               设∑={a，b}，在下表中列出了∑上的一些正规式和相应的正规集。
               
               正规式和相应的正规集
               若两个正规式表示的正规集相同，则认为二者等价。两个等价的正规式U和V记为U=V。例如，b（ab）*=（ba）*b，（a|b）*=（a*b*）*。
               有限自动机
               有限自动机是一种识别装置的抽象概念，它能准确地识别正规集。有限自动机分为两类：确定的有限自动机和不确定的有限自动机。
               （1）确定的有限自动机（Deterministic Finite Automata，DFA）。一个确定的有限自动机是个五元组：（S，∑，f，s0，Z），其中：
               ①S是一个有限集合，它的每个元素称为一个状态。
               ②∑是一个有穷字母表，它的每个元素称为一个输入字符。
               ③f是S×∑→S上的单值部分映像。f（A，a）=Q表示当前状态为A、输入为a时，将转换到下一状态Q。称Q为A的一个后继状态。
               ④s0∈S，是唯一的一个开始状态。
               ⑤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对应的状态转换图和状态转换矩阵如下图所示。
               
               NFA的状态转换图和转换矩阵
               显然，DFA是NFA的特例。实际上，对于每个NFAM，都存在一个DFAN，且L（M）=L（N）。
               词法分析器的任务是把构成源程序的字符流翻译成单词符号序列。手工构造词法分析器的方法是先用正规式描述语言规定的单词符号，然后构造相应有限自动机的状态转换图，最后依据状态转换图编写词法分析器（程序）。
 
本知识点历年真题：
隶属试卷 题号/题型 题干 难度系数/错误率
   2019年下半年
   嵌入式系统设计..
   上午试卷 综合知识 		第18题
选择题
将编译器的工作过程划分为词法分析、语法分析、语义分析、中间代码生成、代码优化和目标代码生成时，语法分析阶段的输入是(18)。若程序中的括号不配对，则会在(19)阶段检查出该错误。

62%
   2015年下半年
   嵌入式系统设计..
   上午试卷 综合知识 		第19题
选择题
编译器和解释器是两种基本的高级语言处理程序。编译器对高级语言源程序的处理过程可以划分为词法分析、语法分析、语义分析、中间代码生成、代码优化、目标代码生成等阶段，其中，(19)并不是每个编译器都必需的。与编译器相比，解释器(20)..

41%
 
 相关知识点：
词法分析
中间代码生成
程序设计语言的翻译基础
出错处理
代码优化
编译器基础
语义分析
解释器基础
语法分析
符号表管理
语法分析
目标代码生成
 
软考在线指南
优惠劵及余额
在线支付
修改密码
下载及使用
购买流程
取消订单
联系我们
关于我们
联系我们
商务合作
旗下网站群
高级资格科目
信息系统项目管理师 系统分析师
系统架构设计师 网络规划设计师
系统规划与管理师
初级资格科目
程序员 网络管理员
信息处理技术员 信息系统运行管理员
中级资格科目
系统集成项目管理工程师 网络工程师
软件设计师 信息系统监理师
信息系统管理工程师 数据库系统工程师
多媒体应用设计师 软件评测师
嵌入式系统设计师 电子商务设计师
信息安全工程师
 

本网站所有产品设计（包括造型，颜色，图案，观感，文字，产品，内容），功能及其展示形式，均已受版权或产权保护。
任何公司及个人不得以任何方式复制部分或全部，违者将依法追究责任，特此声明。
本站部分内容来自互联网或由会员上传，版权归原作者所有。如有问题，请及时联系我们。

工作时间：9:00-20:00

客服

点击这里给我发消息 点击这里给我发消息 点击这里给我发消息

商务合作

点击这里给我发消息

客服邮箱service@rkpass.cn


京B2-20210865 | 京ICP备2020040059号-5 |京公网安备 11010502032051号 | 营业执照 | Copyright ©2000-2023 All Rights Reserved 软考在线版权所有