如果我已经实现了基本的正则表达式匹配器,我如何实现词法分析器？

Question

我正在尝试实现一个有趣的词法分析器.我已经实现了一个基本的正则表达式匹配器(首先将模式转换为NFA,然后转换为DFA).现在我对如何继续我一无所知.

我的词法分析者将会获取一系列令牌及其相应的正则表达式.用于创建词法分析器的一般算法是什么？

我想过(或)所有的正则表达式,但后来我无法确定哪个特定的令牌匹配.即使我扩展我的正则表达式模块以返回匹配成功时匹配的模式,我如何在匹配器中实现先行？

Answer 1

假设你有一个正在运行的正则表达式,regex_match它返回一个布尔值(如果一个字符串满足正则表达式,则返回True).首先,您需要有一个有序的令牌列表(每个令牌都有正则表达式)tokens_regex,订单很重要,因为订单将规定优先顺序.

一种算法可能是(这不一定是唯一的算法):

1. 编写一个next_token接受字符串的过程,并返回第一个标记,其值和剩余字符串(或者 - 如果是非法/忽略字符 - 无,有问题的字符和剩余的字符串).注意:这必须尊重优先权,并且应该找到最长的令牌.
2. 编写一个lex递归调用的过程next_token.

.

像这样的东西(用Python编写):

tokens_regex = [ (TOKEN_NAME, TOKEN_REGEX),...] #order describes precedence

def next_token( remaining_string ):
    for t_name, t_regex in tokens_regex: # check over in order of precedence
        for i in xrange( len(remaining_string), 0, -1 ): #check longest possibilities first (there may be a more efficient method).
            if regex_match( remaining_string[:i], t_regex ):
                return t_name, remaining_string[:i], remaining_string[i:]
    return None, remaining_string[0], remaining_string[1:] #either an ignore or illegal character

def lex( string ):
    tokens_so_far = []
    remaining_string = string
    while len(remaining_string) > 0:
        t_name, t_value, string_remaining = next_token(remaining_string)
        if t_name is not None:
            tokens_so_far.append(t_name, t_value)
        #elif not regex_match(t_value,ignore_regex):
            #check against ignore regex, if not in it add to an error list/illegal characters
   return tokens_so_far

要添加一些内容以改进词法分析器:忽略正则表达式,错误列表和位置/行号(对于这些错误或令牌).

玩得开心!并且好运做一个解析器:).