编译原理之词法分析

前端之家收集整理的这篇文章主要介绍了编译原理之词法分析前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。


词法分析:

编译程序的第一步工作,编译程序的一部分。

核心作用,将字符序列转化为计算机的内部表示

读出字符序列,逐个拼出单词,并构造相应的内部表示。

检查词法错误

例如对于字符序列源文件,经过词法分析

if (position > 10) rate = 3.14 * initial;

则应该产生下面的内容

<$if,->,<$open,<$id,position>,<$gt,<$num,10>

<$close,rate>,<$eq,3.14>,<$mult,

<$id,initial><$semi,->

词法分析器的接口:

1,仅仅作为语法分析的子程序

read

call

Src词法分析语法分析

Char

Token

2 另一类作为编译器的独立一遍处理器

srcchar 词法分析 Token 语法分析

在这里我们讲述一下单词的含义:

单词:指的是语言中具有独立含义的最小单位。对于上面的程序语句而言。

if (position > 10) rate = 3.14 * initial;

这条语句,在词法分析的阶段我们考录3.14这个字符序列。我们可以有多种单词构成。例如

3.14 * initial这三个部分,当然这是表达式乘积,但是倘若我们再进一步的把3.14分为3 . 14

这样的划分方式就不太合理了。因为对于我们而言,3.14作为一个具有独立含义的单位,表示数字

在一个程序中,单词可以分为下列几类:

保留字:-------whiledo

标识符:identifier a,b,class T

Word

常量:

true

10 A

1 运算符 + -* /

2 界限符 { }

特殊符号:

3 格式符 EOF

那么如何实现词法程序:

需求:

描述方式

算法正则表达式

单词的描述工具分为两种:

自动

字母表:。程序中所有可能出现的符号。A / - j 等等

符号串:符号组成的任意有穷序列

符号串的连接:

ɑ,β 分别为字母表组成的符号串,ɑ = abc β = def

则两者的连接为:ɑβ = abcdef

符号串的方幂

符号串集合的乘积

A B分别是两个符号串集合,其中A = {ab,cd},B = {ef,gh}

AB的的乘积还是一个集合{abef,abgh,cdef,cdgh}

而方幂则表示为

假如符号串集合为A = {a,b}

则A0={e},A1=A, A2=AA,…,An=AA… A

A3次方幂为AAA = (AA)A ={aa,ab,ba,bb}{a,b} = {aaa,aba,baa,bba,aab,abb,bab,bbb}

符号串的正闭包

A是符号串集合,则A+称为符号串集合A的正闭包

A+ = A+=A1A2A3 …An…

符号串集合的的星闭包

A* =A0A1A2A3 …An…=A0A+

正则表达式的定义:

为字母表,RE为定义在的正则表达式,则有

正则表达式对应的语义解释被称作正则集,正则集也是正则表达式所对应的语言。

在词法分析中,正则表达式是针对单词进行描述的,为此,我们要建立一种从正则表达式到字符串集合的映射关系。

使得正则表达式的语义解释描述成字符串的形式。

e,e1,e2上的正则表达式,则e所对应的正则集L(e)取值如下:

正则表达式的性质:

+ = * > . > |运算优先级

A | B = B | A

A | (B | C) = A ( B | C) |的可结合性

A|(BC) = (AB) | (AC) 连接的可分配性

A** = A* 幂的等价性

用正则表达式表示描述词法:

L= A|BC|D|……|a|b|……|z

D = 0|1|2|……|9 D1 = 1|2|3|……|9

标识符:(L|(L|D)*

常数: +|-|Φ|D1D*|0

实数: +|-|Φ|D1D*|0.D*

特殊符号:使用枚举

保留字: while | if | do|……

运算符: +|-|*|……

分界符: { | } | |……

控制符: \t \n

当然正则表达式不仅仅可以用于词法分析也可以在其它的地方使用,例如手机号码归属地,程序分析技术等等。

正则表达式的局限性:

正则表达式缺乏对对称性字符串的表达能力。

原文链接:https://www.f2er.com/regex/360671.html

猜你在找的正则表达式相关文章