Python スタイルのインデント用の PEG

https://stackoverflow.com/questions/4205442

25-09-2019
|

質問

どのように書きますか式の文法の解析次のパーサージェネレーターのいずれか (PEG.js, 柑橘類, 梢) Python/Haskell/CoffeScript スタイルのインデントを処理できます。

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

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 } }

解決

純粋な 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",
   "",
   ""
]

このトークナイザーは不正なインデントも検出します。

他のヒント

私はそのようなインデントに敏感な言語は文脈依存だと思います。私は、PEGのみ文脈自由langaugesを行うことができると信じています。

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

だから、私たちは本当に多くの場合、自分のレキシカルスコープを持つCスタイルのブロックのようなものを作成しているインデントで、ここでやっています。私はそのような言語用のコンパイラを書いていた場合、私は、インデントの字句解析キープトラックを試してみて、持っていると思います。たびにインデントの増加は、それが「{」トークンを挿入することができます。同様に、それはそれを減少させるたびにトークン「}」はめ込むことができます。そして、レキシカルスコープを表現するための明示的な中括弧と式の文法を書くこと、前方よりまっすぐになります。

あなたはセマンティック述語を使用することによって梢でこれを行うことができます。この場合、あなたはホワイトスペースを閉じる検出が原因同じまたは小さいインデントを持つ別のラインの発生にブロックをインデントすることを意味的な述語を必要としています。述語は、オープニングラインからのインデントをカウントし、現在の行のインデントが同じか短い長さで終了している場合（ブロックが閉じ）trueを返す必要があります。クロージング条件はコンテキスト依存なので、メモ化してはいけません。ここで私は梢のドキュメントを追加する程度だサンプルコードです。私は梢のSyntaxNodeをオーバーライドしてきたことを注意それが簡単に結果を視覚化できるようにする方法を調べています。

grammar IndentedBlocks
  rule top
    # Initialise the indent stack with a sentinel:
    &{|s| @indents = [-1] }
    nested_blocks
    {
      def inspect
        nested_blocks.inspect
      end
    }
  end

  rule nested_blocks
    (
      # Do not try to extract this semantic predicate into a new rule.
      # It will be memo-ized incorrectly because @indents.last will change.
      !{|s|
        # Peek at the following indentation:
        save = index; i = _nt_indentation; index = save
        # We're closing if the indentation is less or the same as our enclosing block's:
        closing = i.text_value.length <= @indents.last
      }
      block
    )*
    {
      def inspect
        elements.map{|e| e.block.inspect}*"\n"
      end
    }
  end

 rule block
    indented_line       # The block's opening line
    &{|s|               # Push the indent level to the stack
      level = s[0].indentation.text_value.length
      @indents << level
      true
    }
    nested_blocks       # Parse any nested blocks
    &{|s|               # Pop the indent stack
      # Note that under no circumstances should "nested_blocks" fail, or the stack will be mis-aligned
      @indents.pop
      true
    }
    {
      def inspect
        indented_line.inspect +
          (nested_blocks.elements.size > 0 ? (
            "\n{\n" +
            nested_blocks.elements.map { |content|
              content.block.inspect+"\n"
            }*'' +
            "}"
          )
          : "")
      end
    }
  end

  rule indented_line
    indentation text:((!"\n" .)*) "\n"
    {
      def inspect
        text.text_value
      end
    }
  end

  rule indentation
    ' '*
  end
end

あなたは簡単にそれを試すことができますので、ここで少しテストドライバプログラムがあります：

require 'polyglot'
require 'treetop'
require 'indented_blocks'

parser = IndentedBlocksParser.new

input = <<END
def foo
  here is some indented text
    here it's further indented
    and here the same
      but here it's further again
      and some more like that
    before going back to here
      down again
  back twice
and start from the beginning again
  with only a small block this time
END 

parse_tree = parser.parse input

p parse_tree

私は、これは古いスレッドですけど、私はただの答えに、いくつかの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"

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow