1

ファイル内のパスを解析する文法を PLY で書こうとしています。シフト削減の競合が発生していますが、文法を変更して修正する方法がわかりません。解析しようとしているファイルの例を次に示します。パス/ファイル名は、受け入れ可能な任意の Linux パスにすることができます。

file : ../../dir/filename.txt
file : filename.txt
file : filename

だからここに私が書いた文法があります。

header : ID COLON path

path : pathexpr filename

pathexpr : PERIOD PERIOD DIVIDE pathexpr
           | PERIOD DIVIDE pathexpr
           | ID DIVIDE pathexpr 
           |
filename : ID PERIOD ID
           | ID

これが私のトークンです。PLY に含まれる ctokens ライブラリを使用しています。自分で書く手間を省くためです。

t_ID = r'[A-Za-z_][A-Za-z0-9_]*'
t_PERIOD = r'\.'
t_DIVIDE = r'/'
t_COLON = r':'

したがって、パーサーはトークンを「ID」に減らすか、「ID PERIOD ID」にシフトするかがわからないため、「ファイル名」ルールにシフト削減の競合があると思います。パス（「ファイル名」）がない場合、空に減らす代わりにpathexprでトークンを消費する別の問題があると思います。

これらのケースを処理するために文法を修正するにはどうすればよいですか? たぶん、トークンを変更する必要がありますか?

4

3 に答える 3

0

簡単な解決策: 右再帰の代わりに左再帰を使用します。

LR パーサー (PLY や yacc など)は、パーサー スタックを拡張する必要がないため、左再帰を好みます。また、通常は式のセマンティクスに近くなります。これは、言語を認識するだけでなく、実際に解釈したい場合に役立ちます。また、この場合のように、多くの場合、左因数分解の必要がなくなります。

この場合、たとえば、pathexpr現在見つかっているディレクトリ内のセグメント ディレクトリを検索して、各パス セグメントを先行する に適用する必要があります。パーサーのアクションは明確です: $1 で $2 を検索します。適切な再帰バージョンのアクションをどのように修正しますか?

したがって、簡単な変換：

header   : ID COLON path

path     : pathexpr filename

pathexpr : pathexpr PERIOD PERIOD DIVIDE
         | pathexpr PERIOD DIVIDE
         | pathexpr ID DIVIDE
         |
filename : ID PERIOD ID
         | ID
于 2015-09-28T19:38:17.213 に答える