Представление необязательного синтаксиса и повторения с OcamlYacc / FsYacc - PullRequest
Новая
       34

Представление необязательного синтаксиса и повторения с OcamlYacc / FsYacc

3 голосов
/ 10 февраля 2009

Я пытаюсь развить некоторые навыки в грамматике лексизма / разбора. Я оглядываюсь назад на простой синтаксический анализатор, который я написал для 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?

Ответы [ 2 ]

3 голосов
/ 26 июня 2009

Менгир позволяет параметризовать нетерминальные символы другими символами и предоставляет библиотеку стандартных сочетаний клавиш, таких как дополнительные и списки, и вы можете создавать свои собственные. Пример: 

option(X): x=X { Some x} 
         | { None }

Существует также некоторый синтаксис сахара, 'токен?' эквивалентно 'option (token)', 'token +' и 'nonempty_list (token)'.

Все это действительно сокращает определение грамматики. Также он поддерживается ocamlbuild и может быть заменой ocamlyacc. Настоятельно рекомендуется!

Забавно, я тоже использовал его для разбора SQL:)

3 голосов
/ 10 февраля 2009

Когда вы составляете все маленькие кусочки, вы должны получить что-то, что хотите. Вместо: 

(INNER | RIGHT | LEFT )

у вас просто есть 

inner_right_left

и определите, что это объединение этих трех ключевых слов.

Вы также можете определить объединение в лексере. в том, как вы определяете токены или используете camlp4, я мало что сделал в этой области, поэтому я не могу посоветовать вам пойти по этим маршрутам. И я не думаю, что они будут работать для вас так же, как просто иметь маленькие кусочки повсюду.

EDIT:

Итак, для camlp4 вы можете посмотреть Модуль грамматики Camlp4 и учебник и лучший учебник . Заметьте, это не точно , но вы довольно близко. Документация довольно плохая, как выражено в недавнем обсуждении групп ocaml , но я не думаю, что у вас будет слишком много проблем. Я немного с этим справился и могу задать больше вопросов.

...