编译原理（一）词法分析

词法分析（Lexical analysis）是完成编译程序的第一个阶段的工作。

词法分析是从左到右一个字符一个字符地读入源程序，即对构成源程序的字符流进行扫描然后根据构词规则识别单词(也称单词符号或符号)。词法分析程序实现这个任务。词法分析程序可以使用lex等工具自动生成。

关键字

词法分析主要任务就是需要把由代码组成的字符串来识别出来，生成可以被识别的关键字序列。

图片1

本文只实现了5种关键字类型，其中IGN是可悲忽略的字符，

1
2
3
4
5
6
7
# 关键字类型
class TOKENTYPE(object):
    IGN = 0 # ignore
    OPT = 1 # oprate
    SCP = 1 # reserved
    INT = 2 # int
    STR = 3 # string

对于不同的关键字需要对应的正则表达式来匹配该数据，并且需要预设关键字的优先级，例如，乘号的优先级高于加号，

1
2
3
4
5
6
7
8
# 关键字定义
class TokenRegex(object):
    def __init__(self, regex, name,type=TOKENTYPE.OPT, priority=1):
        self.regex = regex
        self.name = name
        self.type = type
        self.priority = priority
        self.value = None

关键字定义如下，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
_TokenRegexs = (
    TokenRegex(r'\=', 'eq'),
    TokenRegex(r'\+', 'add'),
    TokenRegex(r'\-', 'sub'),
    TokenRegex(r'\*', 'mux', priority=2),
    TokenRegex(r'\/', 'div', priority=2),
    TokenRegex(r'\(', '(', type=TOKENTYPE.SCP, priority=3),
    TokenRegex(r'\)', ')', type=TOKENTYPE.SCP, priority=3),
    TokenRegex(r'\{', '{', type=TOKENTYPE.SCP, priority=3),
    TokenRegex(r'\}', '}', type=TOKENTYPE.SCP, priority=3),
    TokenRegex(r'if', '_if'),
    TokenRegex(r'else', '_else'),
    TokenRegex(r';', 'end'),
    TokenRegex(r'[0-9]+', 'int',  type=TOKENTYPE.INT),
    TokenRegex(r'[a-zA-Z][a-zA-Z0-9_]*', 'str', type=TOKENTYPE.STR),
    TokenRegex(r'\n', 'enter', type=TOKENTYPE.IGN),
    TokenRegex(r' ', 'blank', type=TOKENTYPE.IGN),
)

此外，还需要定义特殊关键子匹配规则，

1
2
3
4
TOKEN_SCP_MATCH = {
    '(':  ')',
    '{':  '}',
}

递归遍历输入字符，生成对应的关键字链表，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def lex(characters):
    pos = 0 
    length = len(characters)
    while pos < length:
        for token_regex in _TokenRegexs:
            regex = re.compile(token_regex.regex)
            r = regex.match(characters, pos)
            if r:
                if token_regex.type is not TOKENTYPE.IGN:
                    yield Token(r.group(0), token_regex)
                pos = r.end(0)
                break
        else:
            print 'char:', characters[pos]
            sys.stderr.write('Illgal character: %s\n' % characters[pos])
            sys.exit(1)

关键字识别

关键字识别单元，用来存储每一个关键字的信息

1
2
3
4
5
6
7
8
9
10
11
12
class Token(object):
    def __init__(self, value, token_regex):
        self.value = int(value) if value.isdigit() else value
        self.name = token_regex.name
        self.type = token_regex.type
        self.priority = token_regex.priority

    def __repr__(self):
        return '<Token(\'%s\') %s %s>' % (self.name, self.value, self.priority)

    def is_end(self):
        return True if self.name == 'end' else False