PEG für Python-Stil Einzug
-
25-09-2019 - |
Frage
Wie würden Sie einen Parsing Expression Grammatik in einem der folgenden Parser-Generatoren ( PEG.js , Treetop ), die Python / Haskell / Coffeescript Stil Einzug verarbeiten kann:
Beispiele für einen noch nicht vorhandenen Programmiersprache:
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
Update: Versuchen Sie nicht, einen Interpreter für die obigen Beispiele zu schreiben. Ich bin nur in der Vertiefung Problem interessiert. Ein weiteres Beispiel könnte die folgende sein Parsen:
foo
bar = 1
baz = 2
tap
zap = 3
# should yield (ruby style hashmap):
# {:foo => { :bar => 1, :baz => 2}, :tap => { :zap => 3 } }
Lösung
Reines PEG kann nicht Parse-Einzug.
Aber peg.js können.
Ich habe ein schnelles und unsauberes Experiment (von Ira Baxter Kommentar inspiriert über Betrug) und schrieb ein einfaches tokenizer.
Für eine vollständigere Lösung (ein vollständiger Parser) bitte diese Frage finden Sie unter: Parst Einrückungsebene mit 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
ist ein Stapel von Vertiefungen. indent () gibt ein Array von Einbuchtung Token zurück und starten () das Array auspackt den Parser verhalten sich etwas wie ein Strom zu machen.
peg.js produziert für den Text:
alpha
beta
gamma
delta
epsilon
zeta
eta
theta
iota
diese Ergebnisse:
[
"alpha",
"INDENT",
"beta",
"gamma",
"INDENT",
"delta",
"DEDENT",
"DEDENT",
"epsilon",
"INDENT",
"zeta",
"DEDENT",
"BADDENT",
"eta",
"theta",
"INDENT",
"iota",
"DEDENT",
"",
""
]
Dieser tokenizer sogar fängt schlecht Einzüge.
Andere Tipps
Ich denke, eine Vertiefung sensible Sprache wie das ist kontextsensitiv. Ich glaube, PEG kann nur kontextfreien langauges tun.
Beachten Sie, dass, während nalply Antwort der ist sicher richtig, dass PEG.js es über externen Staat tun kann (dh die gefürchteten globalen Variablen), kann es ein gefährlicher Weg zu gehen nach unten (schlechter als die üblichen Problemen mit globalen Variablen). Einige Regeln können zunächst übereinstimmen (und dann ihre Aktionen ausgeführt werden), aber Eltern Regeln können somit nicht die Aktion Lauf verursacht ungültig. Wenn externe Zustand in eine solche Aktion geändert wird, können Sie sich mit ungültigen Zustand beenden. Das ist super schrecklich, und könnte zu Zittern, Erbrechen und Tod führen. Einige Probleme und Lösungen dafür sind in den Kommentaren hier: https://github.com/dmajda/pegjs / issues / 45
Also, was wir wirklich hier tun mit Vertiefung ist so etwas wie ein C-Stil Blöcke zu schaffen, die oft ihren eigenen lexikalischen Gültigkeitsbereich haben. Wenn ich einen Compiler für eine Sprache schrieben, dass ich glaube, ich würde versuchen, die Lexer verfolgen die Vertiefung haben. Jedes Mal, erhöht sich die Einbuchtung es einfügen könnte ‚{‘ token. Ebenso jedes Mal, wenn es abnimmt könnte ein ‚}‘ token nach innen versetzt. Dann einen Ausdruck Grammatik mit expliziten geschweiften Klammern schreiben lexikalischer darstellen Umfang mehr geradlinig wird.
Sie können diese mithilfe von semantischen Prädikaten in Treetop tun. In diesem Fall müssen Sie ein semantisches Prädikat, das erkennt einen weißen Raum eingerückt Block aufgrund des Auftretens einer anderen Leitung zu schließen, die die gleichen oder geringere Vertiefung hat. Das Prädikat muss die Vertiefung von der Öffnung Linie zählen, und return true (Block geschlossen), wenn die Einrückung der Stromleitung von der gleichen oder kürzerer Länge fertig gestellt. Da der Schließzustand kontextabhängig ist, darf es nicht memoized werden. Hier ist der Beispielcode ich bin zu Treetop Dokumentation hinzuzufügen. Beachten Sie, dass ich habe Treetop die SyntaxNode inspizieren Methode außer Kraft gesetzt, um es einfacher das Ergebnis sichtbar zu machen.
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
Hier ist ein kleines Test-Treiberprogramm, so dass Sie es leicht ausprobieren können:
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
Ich weiß, das ist ein alter Thread, aber ich wollte nur etwas PEGjs Code auf die Antworten hinzuzufügen. Dieser Code wird ein Stück Text und „Nest“ in eine Art „AST-ish“ Struktur analysiert. Es geht nur eine tief und es sieht hässlich aus, außerdem ist es nicht wirklich die Rückgabewerte verwenden, um die richtige Struktur zu schaffen, sondern hält einen speicherinternen Baum Ihrer Syntax und es wird wieder, dass am Ende. Dies könnte auch unhandlich und einige Performance-Probleme verursachen, aber zumindest tut es das, was es soll.
Hinweis: Kontrollieren Sie, ob Tabs statt Leerzeichen
{
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"