13

Terence Parr による Definitive ANTLR リファレンスを読んでいます。

セマンティック述語は、ランタイム情報が認識を駆動できるようにすることで、コンテキスト依存の言語構造を認識する強力な手段です。

しかし、この本の例は非常に単純です。私が知る必要があるのは、ANTLR は次のような状況依存のルールを解析できるかということです。

xAy --> xBy

ANTLR がこれらの規則を解析できない場合、文脈依存の文法を扱う別のツールはありますか?

4

2 に答える 2

11

ANTLR は、LL(*) である文法のみを解析します。あなたが提供した例のような完全な文脈依存言語の文法を使用して解析することはできません。Parr が意味したことは、ANTLR がいくつかの(左の) コンテキスト制約を必要とするいくつかの言語を解析できるということだったと思います。

特に、「リダクション アクション」でセマンティック述語を使用できます (これは、DMS ソフトウェア リエンジニアリング ツールキットで使用される GLR パーサーに対して行いますが、考え方は ANTLR の場合と似ていると思います)。これまでパーサーによって収集されたデータを検査します。他のセマンティック アクションのアドホックな副作用として、または部分的に構築された解析ツリーで。

DMS ベースのDMS ベースの Fortran フロント エンドでは、DO ループが適切に配置されていることを確認するための状況依存チェックがあります。検討：

 DO  20, I= ...
   DO 10, J = ...
       ...
20  CONTINUE
10  CONTINUE

パーサーの観点からは、レキシカル ストリームは次のようになります。

DO  <number> , <variable> =  ...
    DO <number> , <variable> = ...
         ...
<number> CONTINUE
<number> CONTINUE

パーサーは、どの DO ステートメントがどの CONTINUE ステートメントに対応しているかをどのように知ることができますか? (FORTRAN は複数の DO ヘッドで CONTINUE ステートメントを共有できるため、各 DO が最も近い CONTINUE に一致するとは言えません)。

次のルールのリダクションでセマンティック述語「CheckMatchingNumbers」を使用します。

block = 'DO' <number> rest_of_do_head newline 
         block_of_statements
         <number> 'CONTINUE' newline ; CheckMatchingNumbers

DO キーワードに続く番号と CONTINUE キーワードに続く番号が一致することを確認します。セマンティック述語が一致すると言う場合、このルールの削減は成功し、DO ヘッドを正しい CONTINUE に揃えました。述語が失敗した場合、縮小は提案されません (そして、この規則はローカル コンテキストを解析する候補から削除されます)。他の一連のルールでテキストを解析する必要があります。

FORTRAN の入れ子を共有コンティニューで処理するための実際のルールとセマンティック述部は、これよりも複雑ですが、これで意味が通じると思います。

必要なのは、完全な状況依存の解析エンジンです。人々がそれらを構築したことは知っていますが、完全な実装については知りませんし、それらが高速であるとは思っていません。

しばらくの間、 Quinn Taylor Jackson の MetaS 文法システムに従っていました。近づくための実際的な試みのように聞こえました。

于 2011-02-26T23:25:53.127 に答える
0

Prologで状況依存のパーサーを作成するのは比較的簡単です。このプログラムは文字列を解析し、次の[a,is,less,than,b,and,b,is,less,than,c]ように変換し[a,<,b,<,c]ます。

:- initialization(main).
:- set_prolog_flag('double_quotes','chars').

main :-
    rewrite_system([a,is,less,than,b,and,b,is,less,than,c],X),writeln('\nFinal output:'),writeln(X).

rewrite_rule([[A,<,B],and,[B,<,C]],[A,<,B,<,C]).
rewrite_rule([A,is,less,than,B],[A,<,B]).
rewrite_rule([[A,<,B],and,C,than,D],[[A,<,B],and,A,is,C,than,D]).
rewrite_rule([A,<,B],[[A,<,B]]).

rewritten(A) :- atom(A);bool(A).
bool(A) :- atom(A).
bool([A,<,B,<,C]) :- atom(A),atom(B),atom(C).
bool([A,and,B]) :- bool(A),bool(B).


% this predicate is from https://stackoverflow.com/a/8312742/975097
replace(ToReplace, ToInsert, List, Result) :-
    once(append([Left, ToReplace, Right], List)),
    append([Left, ToInsert, Right], Result).

rewrite_system(Input,Output) :-
    rewritten(Input),Input=Output;
    rewrite_rule(A,B),
    replace(A,B,Input,Input1),
    writeln(Input1),
    rewrite_system(Input1,Output).

同じアルゴリズムを使用して、入力から新しい書き換え規則を「学習」する適応パーサーも作成しました。

于 2019-03-17T20:21:19.213 に答える