1

パーサージェネレータに関する限り、明らかな欠陥がある次の文法を見ると:

"Start Symbol" = <Foo>
"Case Sensitive" = True
"Character Mapping" = 'Unicode'

{A} = {Digit}
{B} = [abcdefABCDEF]
{C} = {A} + {B}

Integer = {A}+
HexNumber = {C}+


<ContextA> ::= '[' HexNumber ']'
<ContextB> ::= '{' Integer '}'                      
<Number> ::= <ContextA> | <ContextB>
<Foo> ::= <Number> <Foo>
       | <>

この文法に欠陥がある理由は、スキャナが端末を区別できないため[Integer;HexNumber]です。(1234整数か 16 進数か?!)。

この例で記述されたプロダクションでは、これはビットとは無関係になりますが、プロダクションのコンテキストが整数または 16 進数のどちらが期待されているかを明確にし、スキャナが依然として連携を拒否する文法が存在する可能性があります。

したがって、スキャナーは、16 進トークンまたは整数トークンに関して正しい判断を下すために、パーサーの状態を知る必要があります。

さて、用語の問題です。これは何を意味しているのでしょうか? うーん... 文法ですか? レクサー？それから？文脈依存のレクサー？それとも、明らかにスキャナーの問題であるにもかかわらず、これは文脈依存の文法であると言えるでしょうか? そのような現象を説明するために使用される他の用語はありますか?

4

2 に答える 2

2

文脈依存とは、まったく異なるものを意味します。

より正式な表記法を使用する場合、Ignacio Vazquez-Abrams が言ったように、元の文法はあいまいであり、編集された文法は LR(1) (または LL(1)) でうまく処理できることがわかります。パーサージェネレーター。問題のないバイソンの文法は次のとおりです。

%start number
%%
digit : '0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
hex   : digit
      | 'a' | 'b' | 'c' | 'd' | 'e' | 'f' 
      | 'A' | 'B' | 'C' | 'D' | 'E' | 'F'
decnum: digit | decnum digit
hexnum: hex   | hexnum hex
number: '[' decnum ']'
      | '{' hexnum '}'

もちろん、bison を使用してスキャナを作成することは一般的ではありませんが、確かに可能です。

あなたが考えている問題はこれだと思います.flexを使用してスキャナーを構築すると、次のようになります。

[[:digit:]]+  { yylval.string = strdup(yytext); return DECNUM; }
[[:xdigit:]]+ { yylval.string = strdup(yytext); return HEXNUM; }

Flex はあいまいなトークンを返すことができないため、入力 (の次の部分) が の場合1234、flex は DECNUM または HEXNUM のいずれかを返す必要があります。最初の最長 (「最大マンチ」) ルールは、どちらの方法でも解析できるトークンの場合、フレックス定義で最初に来るパターンが勝つことを意味します。これは、DECNUM パターンが最初に来る必要があることを意味します。そうしないと、トリガーすることが不可能になるからです (その場合、flex は警告を出します)。

しかし、文法に小さな問題があります。文法が HEXNUM を想定している場合、DECNUM を見つける準備をする必要があるからです。文法が明確であれば、それは問題ではありません。非端末をいくつか作成するだけです。

decnum: DECNUM           { $$ = strtol($1, NULL, 10); free($1); }
hexnum: DECNUM | HEXNUM  { $$ = strtol($1, NULL, 16); free($1); }

それはあいまいさ、または文法にまだ存在しないシフト/削減の競合さえも作成しません。

これを試してみたい場合は、bison プロローグでいくつかの型を宣言する必要があります。

%union {
   char* string;
   long  integer;
}
%token <string> HEXNUM DECNUM
%type <integer> hexnum decnum
于 2015-05-16T18:04:57.540 に答える