automaton - 文法のヘルプ (オートマトンの理論)?

Question

こんにちは皆さん、質問があります。オートマトンに関する簡単な質問です。これがこの種の質問をするのに適切な場所であるかどうかわかりません。実際、今年は Compiler Construction のコースがあり、誰かが良いリソースを知っている場合は、ここに投稿することをお勧めします。

最初に、非常に基本的な質問があります。たとえば、次のような式があります: 2+3*5 、この式の文法を書く方法は? あいまいな例とあいまいでない例を1つずつ意味します ありがとう

Answer 1

「[an]式の文法を書く」ことはできません。文法は生産のためのルールです。簡単な例は次のとおりです。

S -> (S)
S -> SS
S -> [empty]

この文法が何をするかわかりますか?

基本的に、これにより、""、"()"、"((()())())" などの文字列を生成できます。「生成」と言ったことに注意してください。論理的には、単一の「S」から始めて、そこから作業を進め、各 S を右側の「生産」に置き換えます。ただし、重要なのは、この方法で生成する文字列は、形式的な意味で「文法的に正しい」ということです。

解析はこれの逆で、文字列を対応する生成順序に変換します。これが複数の方法で実行できる場合、文法はあいまいです。

コンパイラを作成するときは、まず入力を「lex」する必要があります。2+3*5 は NUM ADD NUM TIMES NUM のようなものに lexed する必要があります (それぞれがトークンです)。次に、文法に基づいてトークンを解析して、おそらく次のような「構文ツリー」を構築します。

  _ + _
2        *
      3/   \5

有効な文字列のみが生成されるように、生成用のルールを作成する必要があります。これは少しトリッキーで、ちょっと芸術的なので、詳細がわからないとあまり役に立ちません。

優先順位は、さまざまな非終端記号 (たとえば、S と T) で処理されます。実際のパーサーには、何十ものパーサーがあります。Cには数百があります。それらを巧みに配置することにより、特定のものを他のものよりも先に一致させることができます。