36

Python/Haskell/CoffeScript スタイルのインデントを処理できる次のパーサー ジェネレーター ( PEG.js、Citrus、Treetop ) のいずれかで、解析式文法をどのように記述しますか。

まだ存在しないプログラミング言語の例:

square x =
    x * x

cube x =
    x * square x

fib n =
  if n <= 1
    0
  else
    fib(n - 2) + fib(n - 1) # some cheating allowed here with brackets

更新: 上記の例のインタープリターを作成しようとしないでください。私はインデントの問題にのみ興味があります。別の例として、次の構文解析が考えられます。

foo
  bar = 1
  baz = 2
tap
  zap = 3

# should yield (ruby style hashmap):
# {:foo => { :bar => 1, :baz => 2}, :tap => { :zap => 3 } }
4

5 に答える 5

24

純粋な PEG はインデントを解析できません。

しかし、peg.jsはできます。

私は簡単な実験を行い (不正行為に関する Ira Baxter のコメントに触発されて)、単純なトークナイザーを作成しました。

より完全なソリューション (完全なパーサー) については、次の質問を参照してください: PEG.js でインデント レベルを解析する

/* Initializations */
{
  function start(first, tail) {
    var done = [first[1]];
    for (var i = 0; i < tail.length; i++) {
      done = done.concat(tail[i][1][0])
      done.push(tail[i][1][1]);
    }
    return done;
  }

  var depths = [0];

  function indent(s) {
    var depth = s.length;

    if (depth == depths[0]) return [];

    if (depth > depths[0]) {
      depths.unshift(depth);
      return ["INDENT"];
    }

    var dents = [];
    while (depth < depths[0]) {
      depths.shift();
      dents.push("DEDENT");
    }

    if (depth != depths[0]) dents.push("BADDENT");

    return dents;
  }
}

/* The real grammar */
start   = first:line tail:(newline line)* newline? { return start(first, tail) }
line    = depth:indent s:text                      { return [depth, s] }
indent  = s:" "*                                   { return indent(s) }
text    = c:[^\n]*                                 { return c.join("") }
newline = "\n"                                     {}

depthsくぼみの積み重ねです。indent() はインデント トークンの配列を返し、start() は配列をアンラップしてパーサーをストリームのように動作させます。

peg.jsはテキストに対して次を生成します。

alpha
  beta
  gamma
    delta
epsilon
    zeta
  eta
theta
  iota

これらの結果:

[
   "alpha",
   "INDENT",
   "beta",
   "gamma",
   "INDENT",
   "delta",
   "DEDENT",
   "DEDENT",
   "epsilon",
   "INDENT",
   "zeta",
   "DEDENT",
   "BADDENT",
   "eta",
   "theta",
   "INDENT",
   "iota",
   "DEDENT",
   "",
   ""
]

このトークナイザーは、不適切なインデントもキャッチします。

于 2012-05-22T19:37:18.480 に答える
8

したがって、ここでインデントを使用して実際に行っているのは、独自の字句スコープを持つCスタイルのブロックのようなものを作成することです。そのような言語のコンパイラを作成している場合は、レクサーにインデントを追跡させようと思います。インデントが増えるたびに、「{」トークンが挿入される可能性があります。同様に、減少するたびに「}」トークンを挿入できます。次に、字句スコープを表す明示的な中括弧を使用して式文法を記述すると、より簡単になります。

于 2011-03-09T02:48:04.217 に答える
8

そのようなインデントに敏感な言語は文脈依存だと思います。PEGは文脈自由言語しかできないと思います。

nalplyの答えは確かに正しいが、PEG.jsは外部状態（つまり、恐ろしいグローバル変数）を介してそれを実行できるが、それは危険な道である可能性があることに注意してください（グローバル変数の通常の問題よりも悪い）。一部のルールは最初は一致する（そしてアクションを実行する）ことができますが、親ルールが失敗してアクションの実行が無効になる可能性があります。このようなアクションで外部状態が変更されると、無効な状態になる可能性があります。これは非常にひどいものであり、震え、嘔吐、および死につながる可能性があります。これに対するいくつかの問題と解決策は、ここのコメントにあります：https ://github.com/dmajda/pegjs/issues/45

于 2011-03-09T01:09:46.883 に答える
0

これが古いスレッドであることは知っていますが、回答に PEGjs コードを追加したかっただけです。このコードは、テキストの一部を解析し、一種の「AST っぽい」構造に「ネスト」します。深さは 1 つしかなく、見苦しく見えます。さらに、戻り値を実際に使用して正しい構造を作成するのではなく、構文のメモリ内ツリーを保持し、最後にそれを返します。これは扱いにくくなり、パフォーマンスの問題を引き起こす可能性がありますが、少なくとも想定どおりの動作をします。

注: スペースの代わりにタブがあることを確認してください!

{ 
    var indentStack = [], 
        rootScope = { 
            value: "PROGRAM",
            values: [], 
            scopes: [] 
        };

    function addToRootScope(text) {
        // Here we wiggle with the form and append the new
        // scope to the rootScope.

        if (!text) return;

        if (indentStack.length === 0) {
            rootScope.scopes.unshift({
                text: text,
                statements: []
            });
        }
        else {
            rootScope.scopes[0].statements.push(text);
        }
    }
}

/* Add some grammar */

start
  = lines: (line EOL+)*
    { 
        return rootScope;
    }


line
  = line: (samedent t:text { addToRootScope(t); }) &EOL
  / line: (indent t:text { addToRootScope(t); }) &EOL
  / line: (dedent t:text { addToRootScope(t); }) &EOL
  / line: [ \t]* &EOL
  / EOF

samedent
  = i:[\t]* &{ return i.length === indentStack.length; }
    {
        console.log("s:", i.length, " level:", indentStack.length);
    }

indent
  = i:[\t]+ &{ return i.length > indentStack.length; }
    {
        indentStack.push(""); 
        console.log("i:", i.length, " level:", indentStack.length);
    }

dedent
    = i:[\t]* &{ return i.length < indentStack.length; }
      {
          for (var j = 0; j < i.length + 1; j++) {
              indentStack.pop();
          } 
          console.log("d:", i.length + 1, " level:", indentStack.length);  
      }

text
    = numbers: number+  { return numbers.join(""); } 
    / txt: character+   { return txt.join(""); }


number
    = $[0-9] 

character 
    = $[ a-zA-Z->+]  
__
    = [ ]+

_ 
    = [ ]*

EOF 
    = !.

EOL
    = "\r\n" 
    / "\n" 
    / "\r"
于 2016-08-10T13:34:56.420 に答える