2

私は次の任務を与えられました。

1 文字以上の文字列の言語の再帰文法を書きなさい。各文字列の最初の文字は大文字にする必要があり、文字列内の他のすべての文字は小文字にする必要があります。

文法の章を読み、いくつかの例を調べた後、これが私の試みです:

<goodString> =<UpCh>|<UpCh> <ch> 

<UpCh> = A|B|C...|Z

<ch> = a|b|c...|z

または多分

<goodString> =<UpCh>|<goodString> <ch>

<UpCh> = A|B|C...|Z

<ch> = a|b|c...|z

これは正しいですか？そうでない場合、私は何を間違えましたか?

4

1 に答える 1

3

現在、あなたの文法は再帰的ではありません。再帰文法には、右側で (直接的または間接的に) 自分自身を呼び出す生成が少なくとも 1 つ含まれます。

この場合、それを使用する明白な場所は「不特定数の小文字」です。そのためには、小文字の文字列 (または何でも) を nil として定義するか、小文字の文字列の後に小文字が続くものとして定義します。次に、word大文字の後に小文字の文字列が続きます。

このような場合、小文字の文字列を、文字の後に文字列が続く、または文字列の後に文字が続くものとして定義できることに注意してください。これらは、それぞれ右再帰および左再帰として知られています。文法を実装する可能性がある場合は、再帰降下パーサーには正しい再帰形式が必要であるが、通常はボトムアップ パーサー (yacc などの多くのジェネレーターなど) には左再帰形式が好まれることを知りたいと思うでしょう。 、Bison、byaccなど、プロデュース）。

于 2013-10-14T04:39:36.643 に答える