Как определить непризнанные правила в Ocamlyacc

Question

Я работаю над компанией projet, где мне нужно создать компилятор для языка с использованием Ocamlyacc и Ocamllex. Я хочу знать, можно ли определить правило в моем Parser Ocamlyacc, которое может сказать мне, что никакие правила моей грамматики не соответствуют синтаксису ввода.

Я настаиваю, что i'am новичок в Ocamllex/Ocamlyacc

Спасибо вам большое за вашу помощь.

Answer 1

Если правил в вашей грамматике не соответствует входу, то Parsing.Parse_error исключения. Обычно это то, что вы хотите.

Существует также специальный токен под названием error, который позволяет повторно синхронизировать состояние анализатора. Вы можете использовать его в своих правилах, поскольку это был настоящий токен, созданный лексером, cf., eof.

Кроме того, я бы предложил использовать menhir вместо более почтенного ocamlyacc. Он легче использовать и отлаживать, а также имеет хорошую библиотеку предопределенных грамматик.

Answer 2

Когда вы пишете компилятор для языка, первым шагом является запуск вашего лексера и проверка правильности вашей программы с лексической точки зрения.

Смотрите пример ниже:

{ 
    open Parser  (* The type token is defined in parser.mli *) 
    exception Eof 
} 
    rule token = parse 
      [' ' '\t']  { token lexbuf }  (* skip blanks *) 
      | ['\n' ]  { EOL } 
      | ['0'-'9']+ as lxm { INT(int_of_string lxm) } 
      | '+'   { PLUS } 
      | '-'   { MINUS } 
      | '*'   { TIMES } 
      | '/'   { DIV } 
      | '('   { LPAREN } 
      | ')'   { RPAREN } 
      | eof   { raise Eof } 

Это лексер признать некоторые арифметические выражения.

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

%token <int> INT 
     %token PLUS MINUS TIMES DIV 
     %token LPAREN RPAREN 
     %token EOL 
     %left PLUS MINUS  /* lowest precedence */ 
     %left TIMES DIV   /* medium precedence */ 
     %nonassoc UMINUS  /* highest precedence */ 
     %start main    /* the entry point */ 
     %type <int> main 
     %% 
     main: 
      expr EOL    { $1 } 
     ; 
     expr: 
      INT      { $1 } 
      | LPAREN expr RPAREN  { $2 } 
      | expr PLUS expr   { $1 + $3 } 
      | expr MINUS expr   { $1 - $3 } 
      | expr TIMES expr   { $1 * $3 } 
      | expr DIV expr   { $1/$3 } 
      | MINUS expr %prec UMINUS { - $2 } 
     ; 

Это небольшая программа для анализа арифметического выражения. На этом этапе программа может быть отклонена, потому что нет правила грамматики, которое необходимо применить, чтобы получить AST в конце. Невозможно определить непризнанные правила, но вам нужно написать грамматику, определяющую способ принятия или отклонения программы.

let _ = 
    try 
    let lexbuf = Lexing.from_channel stdin in 
    while true do 
     let result = Parser.main Lexer.token lexbuf in 
     print_int result; print_newline(); flush stdout 
    done 
    with Lexer.Eof -> 
    exit 0 

Если при компиляции лексера, синтаксический анализатор и последняя программа, у вас есть:

1. 1 + 2 принимается, потому что нет никакой ошибки лексических ошибок и AST может быть построить соответствующее это выражение ,
2. 1 ++ 2 отклонено: нет лексических ошибок, но нет правила строить такой АСТ.

Вы можете нашел больше документации здесь: http://caml.inria.fr/pub/docs/manual-ocaml-4.00/manual026.html