Я пытаюсь развить некоторые навыки в грамматике лексизма / разбора. Я оглядываюсь назад на простой синтаксический анализатор, который я написал для SQL, и я не совсем доволен им - похоже, должен был быть более простой способ написания парсера.
SQL сбил меня с толку, потому что в нем много необязательных токенов и повторений. Например:
SELECT *
FROM t1
INNER JOIN t2
INNER JOIN t3
WHERE t1.ID = t2.ID and t1.ID = t3.ID
Эквивалентно:
SELECT *
FROM t1
INNER JOIN t2 ON t1.ID = t2.ID
INNER JOIN t3 on t1.ID = t3.ID
Предложения ON
и WHERE
являются необязательными и могут встречаться более одного раза. Я обработал это в моем парсере следующим образом:
%{
open AST
%}
// ...
%token <string> ID
%token AND OR COMMA
%token EQ LT LE GT GE
%token JOIN INNER LEFT RIGHT ON
// ...
%%
op: EQ { Eq } | LT { Lt } | LE { Le } | GT { Gt } | GE { Ge }
// WHERE clause is optional
whereClause:
| { None }
| WHERE whereList { Some($2) }
whereList:
| ID op ID { Cond($1, $2, $3) }
| ID op ID AND whereList { And(Cond($1, $2, $3), $5) }
| ID op ID OR whereList { Or(Cond($1, $2, $3), $5) }
// Join clause is optional
joinList:
| { [] }
| joinClause { [$1] }
| joinClause joinList { $1 :: $2 }
joinClause:
| INNER JOIN ID joinOnClause { $3, Inner, $4 }
| LEFT JOIN ID joinOnClause { $3, Left, $4 }
| RIGHT JOIN ID joinOnClause { $3, Right, $4 }
// "On" clause is optional
joinOnClause:
| { None }
| ON whereList { Some($2) }
// ...
%%
Другими словами, я обработал необязательный синтаксис, разбив его на отдельные правила, и обработал повторение с помощью рекурсии. Это работает, но разбивает анализ на кучу маленьких подпрограмм, и очень трудно понять, что на самом деле представляет грамматика.
Я думаю, было бы гораздо проще написать, если бы я мог указать необязательный синтаксис в скобках и повторение с помощью * или +. Это уменьшит мои правила whereClause и joinList до следующего:
whereClause:
| { None }
// $1 $2, I envision $2 being return as an (ID * op * ID * cond) list
| WHERE [ ID op ID { (AND | OR) }]+
{ Some([for name1, op, name2, _ in $1 -> name1, op, name2]) }
joinClause:
| { None }
// $1, returned as (joinType
// * JOIN
// * ID
// * ((ID * op * ID) list) option) list
| [ (INNER | LEFT | RIGHT) JOIN ID [ON whereClause] ]*
{ let joinType, _, table, onClause = $1;
Some(table, joinType, onClause) }
Я думаю, что эта форма намного легче для чтения и выражает грамматику, которую она пытается записать более интуитивно. К сожалению, я не могу найти ничего в документации по Ocaml или F #, которая бы поддерживала эту запись или что-то подобное.
Существует ли простой способ представления грамматик с дополнительными или повторяющимися токенами в OcamlYacc или FsYacc?