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

我正在尝试实现一个词法分析器来娱乐。我已经实现了一个基本的正则表达式匹配器（首先将模式转换为 NFA，然后转换为 DFA）。现在我对如何继续一无所知。

我的词法分析器将获取令牌列表及其相应的正则表达式。用于创建词法分析器的通用算法是什么？

我考虑过对所有正则表达式进行“或”运算，但随后我无法确定匹配的是哪个特定标记。即使我扩展我的正则表达式模块以在匹配成功时返回匹配的模式，我如何在匹配器中实现前瞻？

假设你有一个有效的正则表达式，regex_match它返回一个布尔值（如果字符串满足正则表达式则为 True）。首先，您需要有一个有序的标记列表（每个标记都带有正则表达式）tokens_regex，顺序很重要，因为顺序将规定优先级.

一种算法可以是（这不一定是唯一的）:

1. 写一个程序next_token它接受一个字符串，并返回第一个标记、其值和剩余字符串（或者 - 如果是非法/忽略字符 - None，则有问题的字符和剩余字符串）。注意：这必须尊重优先级，并且应该找到最长的标记。
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

为了改进词法分析器，需要添加一些内容：忽略正则表达式、错误列表和位置/行号（对于这些错误或标记）。

玩得开心！祝你制作解析器好运:)。