Python スタイルのインデント用の PEG
-
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"