5

楽しみのためにレクサーを実装しようとしています。私はすでに基本的な正規表現マッチャーを実装しています（最初にパターンをNFAに変換し、次にDFAに変換することによって）。今、私はどのように進めるかについて無知です。

私のレクサーは、トークンとそれに対応する正規表現のリストを取得します。これからレクサーを作成するために使用される一般的なアルゴリズムは何ですか？

すべての正規表現を（または）処理することを考えましたが、どの特定のトークンが一致したかを識別できません。一致が成功したときに一致したパターンを返すように正規表現モジュールを拡張した場合でも、マッチャーに先読みを実装するにはどうすればよいですか？

4

2 に答える 2

6

ブール値を返す有効な正規表現があると仮定しますregex_match（文字列が正規表現を満たす場合はTrue）。まず、トークンの順序付きリスト (それぞれに正規表現を使用) が必要です。順序は優先順位を規定するtokens_regexため、重要です。

1 つのアルゴリズムは次のようになります(これが唯一のアルゴリズムであるとは限りません)。

  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

lexer を改善するために追加すること: 正規表現、エラー リスト、場所/行番号 (これらのエラーまたはトークンの場合) を無視します。

楽しむ！そして、パーサーを作って頑張ってください:)。

于 2012-09-03T20:08:14.863 に答える
2

私はほとんど同じことをしました。私が行った方法は、すべての式を 1 つのかなり大きな NFA に結合し、同じものを 1 つの DFA に変換することでした。その際、対応する元の各 DFA で以前に受け入れていた状態とその優先順位を追跡します。

生成された DFA には、状態を受け入れる多くの状態があります。対応する遷移がない文字を受け取るまで、この DFA を実行します。DFA が受け入れ状態にある場合は、元の NFA のうちどの NFA がその受け入れ状態を持っていたかを確認します。優先順位が最も高いトークンが、返されるトークンです。

これは、正規表現の先読みを処理しません。いずれにせよ、これらは通常、レクサーの作業には実際には必要ありません。それがパーサーの仕事です。

このようなレクサーは、実行する DFA が基本的に 1 つしかないため、単一の正規表現とほぼ同じ速度で実行されます。NFA の変換を完全に省略して、アルゴリズムの構築は高速化できますが、実行は遅くなります。アルゴリズムは基本的に同じです。

私が書いた字句解析器のソース コードは、github で自由に入手できます。

于 2012-09-04T14:10:22.897 に答える