1

自分の言語を作成することの難しさをより深く理解するために、私は小さなコンパイラーに取り組んでいます。現在、文法にポインタ機能を追加する段階にありますが、それを実行することで、reduce/reduceの競合が発生しました。

これは、によってコンパイルできる私の文法の簡略化されたバージョンですbnfc。私はhappyパーサジェネレータを使用していますが、これは、reduce/reduceの競合があることを通知するプログラムです。

entrypoints Stmt ;

-- Statements
-------------
SDecl. Stmt ::= Type Ident; -- ex: "int my_var;"
SExpr. Stmt ::= Expr;       -- ex: "printInt(123); "

-- Types
-------------
TInt.      Type ::= "int" ;
TPointer.  Type ::= Type "*" ;
TAlias.    Type ::= Ident ; -- This is how I implement typedefs

-- Expressions
--------------
EMult.     Expr1 ::= Expr1 "*" Expr2 ;
ELitInt.   Expr2 ::= Integer ;
EVariable. Expr2 ::= Ident ;

-- and the standard corecions
_.         Expr  ::= Expr1 ;
_.         Expr1 ::= Expr2 ;

私は文法がどのように機能するかを学習している段階にあります。しかし、私は何が起こるかを知っていると思います。これらの2つのプログラムを検討してください

main(){
  int a;
  int b;
  a * b;
}

と

typedef int my_type;
main(){
  my_type * my_type_pointer_variable;
}

（typedefとのmain(){}部分は関連性がなく、私の文法ではありません。しかし、それらはいくつかの文脈を与えます）

a "*" b最初のプログラムでは、それがとして解析されることを望みます。Stmt ==(SExpr)==> Expr ==(EMult)==> Expr * Expr ==(..)==> Ident "*" Identつまり、基本的にSExprルールを使用してステップを開始します。

同時に、my_type * my_type_pointer_variableルールを使って拡張していきたいと思います。Stmt ==(SDecl)==> Type Ident ==(TPointer)==> Type "*" Ident ==(TAlias)==> Ident "*" Ident。

しかし、文法段階では、識別子が元々型エイリアスなのか変数なのかわかりません。

（1）reduce / reduceの競合を取り除くにはどうすればよいですか？（2）この問題を抱えているのは私だけですか？明らかな解決策はありますか？c文法はこの問題をどのように解決しますか？

これまでのところ、「*」の代わりに「＆」またはその他の記号を使用して言語の構文を変更することに成功しましたが、これは非常に望ましくありません。また、さまざまな公開文法からは理解できず、なぜこの問題が発生しないのかを調べようとしましたが、運が悪かったのです。

そして最後に、どうすればこのような問題を自分で解決できますか？より詳細な出力から私が理解したhappyのは、競合がどのように発生するかということだけです。賢さは、これらの競合を回避する唯一の方法ですか？たとえば、紹介するときに、さらに多くの問題に遭遇するのではないかと心配しています。EIndir. Expr = '*' Expr;

4

1 に答える 1

3

この問題がCパーサーで処理される通常の方法は、一般に「レクサーフィードバックハック」と呼ばれるものです。文法でまったく処理しないという意味での「ハック」です。代わりに、レクサーが識別子を認識すると、その識別子をタイプ名または非タイプ名のいずれかに分類し、ケースごとに異なるトークンを返します（通常、タイプ名である識別子の場合は「TypeIdent」と指定され、他の）。レクサーは、シンボルテーブルの現在の状態を確認することでこの選択を行うため、解析の現在のポイントより前に発生したすべてのtypedefは確認されますが、現在のポイントより後のtypedefは確認されません。これが、Cが各コンパイルユニットで最初に使用する前にtypedefを宣言することを要求する理由です。

于 2013-01-07T00:52:58.303 に答える