とっても古い2016年の記事に構文解析と云えば、BNF か ABNF か EBNFかな？作れたのは字句解析まで・・・orzが放置してたので、やってみた。
wikipediaのBNF表記ではうまく動作しないので、
<expression> ::= <list> | <list> "|" <expression>
<list> ::= <term> | <term> <opt-whitespace> <list>空白の判定を必須とオプションに分け、listの式も面倒な方を優先させ、
<opt-whitespace> ::= /\x20*/
<whitespace> ::= /\x20+/
<expression> ::= <list> <whitespace> "|" <whitespace> <expression> | <list>
<list> ::= <term> <whitespace> <list> | <term>と変更した結果、ソースはこんな感じになった。rule-nameの表現がクドいので変更した。
なお、BNFに空文や改行の無い行が含まれる場合はエラる。
/**
* BNFルールと文法を作成
* @param {string} bnf BNFテキスト
* @param {function} proc mapのproc
* @returns mapまたはbnfパターンの戻り値
*/
parseBNF(bnf, proc) {
const opt_whitespace = this.regexp(/\x20*/);
const whitespace = this.regexp(/\x20+/);
const regexp = this.map(this.regexp(/(\/(?!\\)[^/]*\/)/), (parsed) => { /* regexp */
return parsed;
});
const dqstring = this.map(this.seq(this.token('"'), this.regexp(/(?!\\)[^"]*/), this.token('"')), (parsed) => { /* dqstring */
return parsed.flat().join('');
});
const sqstring = this.map(this.seq(this.token(`'`), this.regexp(/(?!\\)[^']*/), this.token(`'`)), (parsed) => { /* sqstring */
return parsed.flat().join('');
});
const literal = this.choice(dqstring, sqstring, regexp);
const rule_name = this.map(this.seq(this.token('<'), this.regexp(/[A-Za-z0-9-_]+/), this.token('>')), (parsed) => {
// [0]: <
// [1]: rule - name
// [2]: >
return parsed[1];
});
const term = this.map(this.choice(rule_name, literal), (parsed) => { /* term */
return parsed; // literal
});
const list = this.lazy(() => {
return this.map(this.choice(this.seq(term, whitespace, list), term), (parsed) => { /* list */
if (Array.isArray(parsed)) { // term, whitespace, list
return parsed.flat();
}
return parsed; // term
})
});
const expression = this.lazy(() => {
return this.map(this.choice(this.seq(list, whitespace, this.token('|'), whitespace, expression), list), (parsed) => { /* expression */
if (Array.isArray(parsed)) { // list, whitespace, this.token('|'), whitespace, expression
return parsed.flat();
}
return [parsed]; // list ruleの処理を簡素にするため配列で渡す
})
});
const line_end = this.regexp(/[\r\n]+/);
const rule = this.map(this.seq(opt_whitespace, rule_name, opt_whitespace, this.token('::='), opt_whitespace, expression, line_end), (parsed) => { /* rule */
// [0]: opt_whitespace
// [1]: rule_name
// [2]: opt_whitespace
// [3]: this.token('::=')
// [4]: opt_whitespace
// [5]: expression
// [6]: line_end
const rule_name = parsed[1];
const expr = parsed[5];
const expression = expr.filter((token) => token.replace(/\x20+/, '').length > 0);
return { name: rule_name, expression: expression };
});
const syntax = this.lazy(() => {
return this.map(this.many(this.choice(rule, this.seq(rule, syntax))), (parsed) => { /* syntax */
const rules = {};
if (parsed !== undefined && parsed !== null) {
while (0 < parsed.length) {
const p1 = parsed.shift();
rules[p1.name] = p1.expression;
}
}
return rules;
})
});
this.fSpaceSkip = false;
const result = syntax(bnf, 0);
if (!result.success) {
console.log('パース失敗');
} else if (bnf.length !== result.position) {
console.log(`${bnf.length}文字中の${1 + result.position}文字目でパース失敗`);
}
if (proc) {
return proc(result);
}
return result.result;
}
testParseBNF() {
const bnf = `<syntax> ::= <rule> | <rule> <syntax>
<rule> ::= <opt-whitespace> <rule-name> <opt-whitespace> "::=" <whitespace> <expression> <line-end>
<rule-name> ::= "<" /[A-Za-z0-9-_]+/ ">"
<line-end> ::= /[\r\n]+/
<opt-whitespace> ::= /\x20*/
<whitespace> ::= /\x20+/
<expression> ::= <list> <whitespace> "|" <whitespace> <expression> | <list>
<list> ::= <term> <whitespace> <list> | <term>
<term> ::= <rule-name> | <literal>
<literal> ::= '"' <text> '"' | "'" <text> "'" | "\`" <text> "\`" | <regexp>
<regexp> ::= /.+/\n`;
this.parseBNF(bnf, (parsed) => {
const json = JSON.stringify(parsed.result, null, 2);
const text = json
.replace(/\[[\r\n]+/sg, "[")
.replace(/(?!]),[\r\n]+/sg, ",")
.replace(/[\r\n]+\x20+\][\r\n]+/sg, "]\n")
.replace(/[\r\n]+(\s+\],)/sg, "$1\n")
.replace(/\x20+/g, " ")
;
console.log('result: ' + text);
});ソースの色付けが怪しいけど字句解析や文法系は一般的なソースコードの書き方ではないから仕方が無いか？（笑
ともあれ、これを動かして
result: {
"syntax": [ "rule", "|", "rule", "syntax" ],
"rule": [ "opt-whitespace", "rule-name", "opt-whitespace", "\"::=\"", "whitespace", "expression", "line-end" ],
"rule-name": [ "\"<\"", "/[A-Za-z0-9-_]+/", "\">\"" ],
"line-end": [ "/[\r\n]+/" ],
"opt-whitespace": [ "/ */" ],
"whitespace": [ "/ +/" ],
"expression": [ "list", "whitespace", "\"|\"", "whitespace", "expression", "|", "list" ],
"list": [ "term", "whitespace", "list", "|", "term" ],
"term": [ "rule-name", "|", "literal" ],
"literal": [ "'\"'", "text", "'\"'", "|", "\"'\"", "text", "\"'\"", "|", "\"`\"", "text", "\"`\"", "|", "regexp" ],
"regexp": [ "/.+/"]
}と出たので一段落。※RegExpなreplaceで短くなるように編集済み
とにかく、デバッグが大変。
一通り作ってから組み合わせてみて、動かしてもドコまで進行しているのかスグに判らなり迷子になってしまうので、tokenやregexpにブレークポイントを置いて、どの辺まで進行したのか？あたりを付けてから、通る様に文法を組み直した。
正規表現部分は、自身の /(\/(?!\)[^/]*\/)/ が通らないが、ほぼ同義の/.+/で通ったので良しとした。
mapやseqなどはspread-sheetカスタムエレメント3 のソースのまま。その元ネタは「Java パーサコンビネータ 超入門」で公開されたソースです。ソースを読んでもイミフなら元ネタを見た方がいいです。
あとは、各ルールで結果をちゃんとしたトークンに整えれば完成しそう。
/**
* BNFルールと文法を作成
* @param {string} bnf BNFテキスト
* @param {function} proc mapのproc
* @returns mapまたはbnfパターンの戻り値
*/
parseBNF(bnf, proc) {
const opt_whitespace = this.regexp(/\x20*/);
const whitespace = this.regexp(/\x20+/);
const regexp = this.map(this.regexp(/(\/(?!\\)[^/]*\/)/), (parsed) => { /* regexp */
return { regexp: parsed.replaceAll(/\x20/g, "\\x20") };
});
const dqstring = this.map(this.seq(this.token('"'), this.regexp(/(?!\\)[^"]*/), this.token('"')), (parsed) => { /* dqstring */
return { dqstring: parsed[1] };
});
const sqstring = this.map(this.seq(this.token(`'`), this.regexp(/(?!\\)[^']*/), this.token(`'`)), (parsed) => { /* sqstring */
return { sqstring: parsed[1] };
});
const bqstring = this.map(this.seq(this.token('`'), this.regexp(/(?!\\)[^`]*/), this.token('`')), (parsed) => { /* bqstring */
return { bqstring: parsed[1] };
});
const literal = this.choice(dqstring, sqstring, bqstring, regexp);
const rule_name = this.map(this.seq(this.token('<'), this.regexp(/[A-Za-z0-9-_]+/), this.token('>')), (parsed) => {
// [0]: <
// [1]: rule - name
// [2]: >
return { rule_name: parsed[1] };
});
const term = this.map(this.choice(rule_name, literal), (parsed) => { /* term */
return parsed;
});
//
const flatArray = (parsed, typeName) => {
if (Array.isArray(parsed)) {
const stack = parsed.map((p) => {
p = flatArray(p, typeName);
if (p.type === typeName) {
return p.value;
}
if (p[typeName] !== undefined) {
return p[typeName];
}
return p;
});
return stack.flat();
}
return parsed;
}
const list = this.lazy(() => {
return this.map(this.choice(this.seq(term, whitespace, list), term), (parsed) => { /* list */
if (Array.isArray(parsed)) {
parsed = this.removeWhiteSpace(parsed);
const parsed0 = flatArray(parsed, "seq");
return { seq: parsed0 }; // term, whitespace, list
}
return parsed; // term
})
});
const expression = this.lazy(() => {
return this.map(this.choice(this.seq(list, whitespace, this.token('|'), whitespace, expression), list), (parsed) => { /* expression */
if (Array.isArray(parsed)) {
parsed = this.removeWhiteSpace(parsed);
if (parsed[1] === '|') {
const parsed0 = flatArray(parsed[0], "choice");
const parsed2 = flatArray(parsed[2], "choice");
return { choice: [parsed0, parsed2] };
}
return parsed; // list, whitespace, this.token('|'), whitespace, expression
}
return parsed; // list
})
});
const line_end = this.regexp(/[\r\n]+/);
const rule = this.map(this.seq(opt_whitespace, rule_name, opt_whitespace, this.token('::='), opt_whitespace, expression, line_end), (parsed) => { /* rule */
// [0]: opt_whitespace
// [1]: rule_name
// [2]: opt_whitespace
// [3]: this.token('::=')
// [4]: opt_whitespace
// [5]: expression
// [6]: line_end
const rule_name = parsed[1];
const expr = this.removeWhiteSpace(parsed[5]);
return { rule: { name: rule_name, expression: expr } };
});
const syntax = this.lazy(() => {
return this.map(this.many(this.choice(rule, this.seq(rule, syntax))), (parsed) => { /* syntax */
const rules = {};
if (parsed !== undefined && parsed !== null) {
while (0 < parsed.length) {
const p1 = parsed.shift();
rules[p1.rule.name.rule_name] = p1.rule.expression;
}
}
return rules;
})
});
this.fSpaceSkip = false;
const result = syntax(bnf, 0);
if (!result.success) {
console.log('パース失敗');
} else if (bnf.length !== result.position) {
console.log(`${bnf.length}文字中の${1 + result.position}文字目でパース失敗`);
}
if (proc) {
return proc(result);
}
return result.result;
}
/**
* テスト
*/
testParseBNF() {
const bnf = ` <syntax> ::= <rule> | <rule> <syntax>
<rule> ::= <opt-whitespace> <rule-name> <opt-whitespace> "::=" <whitespace> <expression> <line-end>
<rule-name> ::= "<" /[A-Za-z0-9-_]+/ ">"
<line-end> ::= /[\r\n]+/
<opt-whitespace> ::= /\x20*/
<whitespace> ::= /\x20+/
<expression> ::= <list> <whitespace> "|" <whitespace> <expression> | <list>
<list> ::= <term> <whitespace> <list> | <term>
<term> ::= <rule-name> | <literal>
<literal> ::= '"' <text> '"' | "'" <text> "'" | "\`" <text> "\`" | <regexp>
<regexp> ::= /.+/\n`;
this.parseBNF(bnf, (parsed) => {
const json = JSON.stringify(parsed.result, null, 2);
const text = json
;
console.log('result: ' + text);
});
の結果がちょっと長いので最深部の｛｝は手作業で短縮形に編集したものがコレ。
result: {
"syntax": {
"choice": [
{ "rule_name": "rule" },
{
"seq": [
{ "rule_name": "rule" },
{ "rule_name": "syntax" }
]
}
]
},
"rule": {
"seq": [
{ "rule_name": "opt-whitespace" },
{ "rule_name": "rule-name" },
{ "rule_name": "opt-whitespace" },
{ "dqstring": "::=" },
{ "rule_name": "whitespace" },
{ "rule_name": "expression" },
{ "rule_name": "line-end" }
]
},
"rule-name": {
"seq": [
{ "dqstring": "<" },
{ "regexp": "/[A-Za-z0-9-_]+/" },
{ "dqstring": ">" }
]
},
"line-end": { "regexp": "/[\r\n]+/" },
"opt-whitespace": { "regexp": "/\\x20*/" },
"whitespace": { "regexp": "/\\x20+/" },
"expression": {
"choice": [
{
"seq": [
{ "rule_name": "list" },
{ "rule_name": "whitespace" },
{ "dqstring": "|" },
{ "rule_name": "whitespace" },
{ "rule_name": "expression" }
]
},
{ "rule_name": "list" }
]
},
"list": {
"choice": [
{
"seq": [
{ "rule_name": "term" },
{ "rule_name": "whitespace" },
{ "rule_name": "list" }
]
},
{ "rule_name": "term" }
]
},
"term": {
"choice": [
{ "rule_name": "rule-name" },
{ "rule_name": "literal" }
]
},
"literal": {
"choice": [
{
"seq": [
{ "sqstring": "\"" },
{ "rule_name": "text" },
{ "sqstring": "\"" }
]
},
{
"choice": [
{
"seq": [
{ "dqstring": "'" },
{ "rule_name": "text" },
{ "dqstring": "'" }
]
},
{
"choice": [
{
"seq": [
{ "dqstring": "\`" },
{ "rule_name": "text" },
{ "dqstring": "\`" }
]
},
{ "rule_name": "regexp" }
]
}
]
}
]
},
"regexp": { "regexp": "/.+/" }
}大体予想通りの結果が得られたのでBNFについてはコレで終了。
※空白を”\x20″と表現させようとしたが、文字列中にバックスラッシュ(\)があると、テキスト化した時に(\\)に変換してるっぽい。