正規表現、玩具コンパイラの作成、解析、コメント削除

compiler-construction parsing regex
正規表現、玩具コンパイラの作成、解析、コメント削除

私は現在、この本を読んでいます:http://www1.idc.ac.il/tecs/

私は現在、言語のような非常に単純なjava用のコンパイラを作成することを目的とするセクションにいます。 この本は常に_what_が必要であると述べていますが、どのようにすべきかではありません(これは良いことです)。 また、yaccとlexについて説明しており、本のプロジェクトでは自分で学習するためにyaccとlexを避けることを具体的に述べていることにも言及する必要があります。

私は10代目で、トークナイザーを書き始めています。

1)誰でも一般的なアドバイスをいただけますか?正規表現はソースファイルをトークン化するための最良の方法ですか?

2)解析する前にソースファイルからコメントを削除したい-これは難しくありませんが、ほとんどのコンパイラはエラーが発生した行を教えてくれます。コメントを削除すると行数が台無しになります。ジャンクを削除しながら行数を維持するための戦略

前もって感謝します!

  4  1


ベストアンサー

トークナイザー自体は通常、すべての有効なトークンを記述する大きなDFAテーブルを使用して記述されます(トークンは、文字で始まり、他の文字/数字が続き、その後に非文字が続くか、または数字の後に他の数字が続きます非数字/ポイント、または少なくとも1つの数字が続き、その後に非数字などが続くポイントのいずれかなど)。 私が自分で作った方法は、トークナイザーが受け入れるすべての正規表現を特定し、DFAに変換して結合することでした。

ここで、「コメントを削除する」ために、トークンを解析するとき、コメントトークン(コメントを解析するための正規表現、言葉で説明するには長すぎる)を持つことができます。このコメントの解析が終了したら、新しいトークンを解析します。したがって、それを無視します。 あるいは、コンパイラーに渡して処理することもできます(または、無視します)。 どちらのアプローチでも、行番号や行への文字などのメタデータが保持されます。

  • DFA理論*の編集:

すべての正規表現は、パフォーマンス上の理由からDFAに変換(および変換)できます。 これにより、解析のバックトラックが削除されます。 http://lambda.uta.edu/cse5317/notes/node9.html [このリンク]は、これがどのように行われるかを示しています。 最初に正規表現をNFA(バックトラッキングを備えたDFA)に変換してから、有限オートマトンを膨らませてすべてのバックトラッキングノードを削除します。

DFAを構築する別の方法は、常識を使用して手動で行うことです。 たとえば、識別子または数値のいずれかを解析できる有限オートマトンを考えてみましょう。 もちろんこれも十分ではありません。おそらくコメントも追加したいからです。しかし、それは基礎となる構造のアイデアを与えてくれるでしょう。

          A-Z       space
->(Start)----->(I1)------->((Identifier))
     |         | ^
     |         +-+
     |        A-Z0-9
     |
     |          space
     +---->(N1)---+--->((Number)) <----------+
      0-9  | ^    |                          |
           | |    | .       0-9       space  |
           +-+    +--->(N2)----->(N3)--------+
           0-9                   | ^
                                 +-+
                                 0-9

使用される表記法に関するいくつかのメモ、DFAは(開始)ノードから開始し、ファイルから入力が読み取られると矢印を移動します。 どの時点でも、一致するパスは1つだけです。 欠落しているパスは、デフォルトで「エラー」ノードに設定されます。 `((Number))`と `((Identifier))`は、終了の成功ノードです。 それらのノードで、トークンを返します。

したがって、最初から、トークンが文字で始まる場合、一連の文字または数字で続行し、「スペース」(スペース、改行、タブなど)で終了する必要があります。 バックトラッキングはありません。これが失敗すると、トークン化プロセスが失敗し、エラーを報告できます。 解析を続けるには、エラー回復に関する理論書を読む必要があります。これは本当に大きなトピックです。

ただし、トークンが数字で始まる場合は、数字の束または小数点を1つ続ける必要があります。 小数点がない場合は、数字の後に「スペース」が続く必要があります。そうでない場合は、数字の後に数字の束が続き、その後にスペースが続く必要があります。 科学表記法は含めませんでしたが、追加するのは難しくありません。

解析速度を上げるため、これはDFAテーブルに変換され、すべてのノードが垂直線と水平線の両方に配置されます。 このようなもの:

             I1            Identifier  N1      N2      N3      Number
start        letter        nothing     number  nothing nothing nothing
I1           letter+number space       nothing nothing nothing nothing
Identifier   nothing       SUCCESS     nothing nothing nothing nothing
N1           nothing       nothing     number  dot     nothing space
N2           nothing       nothing     nothing nothing number  nothing
N3           nothing       nothing     nothing nothing number  space
Number       nothing       nothing     nothing nothing nothing SUCCESS

これを実行する方法は、開始状態を保存し、入力を文字ごとに読みながらテーブルを移動することです。 たとえば、「1.2」の入力は、start→ N1→ N2→ N3→ Number→ SUCCESSとして解析されます。 いずれかの時点で「nothing」ノードにヒットすると、エラーが発生します。

編集2:テーブルは実際にはnode→ node→ characterではなくnode→ character→ nodeである必要がありますが、この場合は関係なく正常に機能しました。 最後に手作業でコンパイラを書いてからしばらく経ちました。

5


1-はい、正規表現はトークナイザーを実装するのに適しています。 lexのような生成されたトークナイザーを使用する場合、各トークンを正規表現として記述します。 マークの答えをご覧ください。

2-字句解析器は、トークンがトークナイザによって消費されるため、通常行/列情報を追跡するものです。トークンを使用して行/列情報を追跡するか、現在の状態として保持します。 したがって、問題が見つかった場合、トークナイザーは現在地を認識します。 したがって、コメントを処理するとき、新しい行が処理されると、トークナイザーはline_countをインクリメントするだけです。

Lexでは、解析状態を持つこともできます。 多くの場合、複数行のコメントはこれらの状態を使用して実装されるため、より単純な正規表現が可能になります。 「/ 」などのコメントの先頭に一致するものが見つかったら、コメント状態に変更します。これは、通常の状態から排他的に設定できます。 したがって、終了コメントマーカー ‘ /’を探してテキストを使用すると、通常のトークンと一致しません。

この状態ベースのプロセスは、_ “test \” more text “_などのネストされたエンドメーカーを許可するプロセス文字列リテラルにも役立ちます。

1


タイトルとURLをコピーしました