文章责编：陶玉良
看了本文的网友还看了学历| 高考 中考 考研 自考 成考 外语| 四六级 职称英语 商务英语 公共英语 资格| 公务员 报关员 银行 证券 司法 导游 教师 计算机| 等考 软考
工程|一建 二建 造价师 监理师 咨询师 安全师 结构师 估价师 造价员 会计| 会计证 会计职称 注会 经济师 税务师 医学| 卫生资格 医师 药师 [更多]
| 第 1 页：2.5.1 文法及语言形式描述 |
| 第 2 页：2.5.2 词法分析 |
| 第 3 页：2.5.3语法分析 |
| 第 4 页：2.5.4 代码优化 |
2.5.2 词法分析
词法分析的任务是把构成源程序的字符串转换成单词符号串的中间程序。词法规则可用3型文法(正规文法)或正规表达式描述。转换方法有人工的状态转换图方法和有限自动机的自动方法。
这部分主要涉及以下两个方面的内容。
● 正规表达式和正规集
正规表达式是一种极为有用的工具。
例如，对于正规文法
〈标识符〉→〈标识符〉字母
〈标识符〉→〈标识符〉数字
〈标识符〉→字母(31)
所定义的语法范畴〈标识符〉，我们可用如下的式子加以表述：
字母·(字母|数字)*(32)
这就是一个正规式。其中“·”，“|”及“*”分别为“连接”、“或”及“闭包”运算符。上述正规式指明，语法范围〈标识符〉被定义为以字母开头，且其后跟以由零个或多个字母和数字的任意序列。由这些序列所组成的集合，我们称之为相应于正规式(32)的正规集。可见正规式(32)也就刻画了某种程序设计语言的标识符的结构。
如所周知，每一程序设计语言都有它自己的字符集Σ。语言中的每一单词，或者是Σ上的单个字符 (如运算符，分隔符等)，或者是Σ上的字符按一定方式组成的字符串 (如常数、关键字、标识符以及关系运算符等)。这里所说的“按一定方式组成”，也就是对字符或字符串进行一定的“·”，“|”或者“*”运算。因此，如果我们把每类单词均视为一种语言，那么，每一类单词都可用一个正规式来描述，而每一类单词中的全体单词也就组成了相应的正规集。
设Σ为一字母表，则Σ上的正规式及其所表征的正规集可递归地定义如下。
1是一个正规式，相应的正规集为空集。
2ε是一个正规式，相应的正规集为{ε}。
3对于每一a∈Σ，a是一个正规式，相应的正规集为{a}。
4若r,s是正规式，且相应的正规集分别记为Lr及Ls，则
(1) (r)·(s)是正规式，相应的正规集为LrLs;
(2) (r)|(s)是正规式，相应的正规集为Lr∪Ls;
(3) (r)*是正规式，相应的正规集为L*r。
需要注意的是，在上述定义中，圆括号并非正规式的运算符，它们仅用于指示正规式中的子表达式。如果我们规定了上述运算符的优先顺序： “*”最优，“·”次之，最后是“|”，则在不产生混乱的情况下，可将正规式中的括号略去。例如，可将正规式((r·(s*))|r)写成r·s*|r。另一方面，我们也可以在一个正规式中添加括号来改变原来的运算顺序，例如r·(s*|r)。显然，在这种情况下，正规式中的括号不能随便略去。此外，正规式中的连接运算符“·”常被略去。如正规式r·s*|r和r·(s*|r)可分别写为rs*|r和r(s*|r)。
● 有限自动机
有限自动机作为一种识别装置，它能准确地识别正规集。它分为两类：确定的有限自动机(DFA)和不确定的有限自动机(NFA)。在有限自动机理论中，可以通过子集法的算法来实现NFA到DFA的转换。
比如： 
：所有与b为首后跟任意多个a的字
：所有与a为首的字;
：含有两个相继的a或两个相继的b的字。
(需要拷贝)语言L={ambn|m≥0，n≥1}的正规表达式是__A__。 (程序语言)
(1) A. a*bb*B. aa*bb*C. aa*b*D. a*b*
相关推荐：
| 北京 | 天津 | 上海 | 江苏 | 山东 |
| 安徽 | 浙江 | 江西 | 福建 | 深圳 |
| 广东 | 河北 | 湖南 | 广西 | 河南 |
| 海南 | 湖北 | 四川 | 重庆 | 云南 |
| 贵州 | 西藏 | 新疆 | 陕西 | 山西 |
| 宁夏 | 甘肃 | 青海 | 辽宁 | 吉林 |
| 黑龙江 | 内蒙古 |
