Menhir

O Menhir é um gerador de parser LR(1) para a linguagem de programação OCaml. Isto é, o Menhir compila especificações de gramáticas LR(1) para código OCaml.

1. Especificação da gramática

As especificações de gramáticas do Menhir são definidas em ficheiros com a extensão .mly. Uma especificação é composta por uma declaração, um conjunto de regras e um código OCaml final opcional.

Declaração

A declaração inicial de uma especificação contém um código OCaml opcional dentro de %{ }% que é copiado tal e qual para o início do ficheiro OCaml gerado.

De seguida, são definidos os tokens sintáticos que o parser deverá reconhecer através de uma declaração na forma %token [<tipo OCaml>] uid1 ... uidn, onde uid1 ... uidn são os nomes dos tokens (que devem começar com letra maiúscula). Esta declaração pode levar opcionalmente um tipo OCaml, o que faz com que se considere que os tokens carregam consigo um valor desse tipo.

Na declaração, é também possível atribuir regras de associatividade e de prioridade aos tokens, recorrendo para isso às declarações %left uid1 ... uidn, %right uid1 ... uidn e %nonassoc uid1 ... uidn, que atribuem aos tokens associatividade à esquerda, à direita e não associatividade, respetivamente. O nível de prioridade desses tokens é definido da seguinte forma: os tokens de uma declaração %left, %right ou %nonassoc têm um nível de prioridade superior ao dos tokens da declaração anterior e um nível de prioridade inferior ao dos tokens da declaração seguinte.

Através da declaração %type <tipo OCaml> lid1 ... lidn, é possível definir qual é o tipo OCaml dos símbolos não-terminais (cujo nome deve começar com minúscula) lid1 ... lidn.

É definido também na declaração quais são os símbolos iniciais da gramática, usando para isso a declaração %start [<tipo OCaml>] lid1 ... lidn, que leva opcionalmente um tipo OCaml que define o tipo código OCaml gerado por esses símbolos.

Indicamos o fim da declaração escrevendo %%.

Regras da gramática

Uma regra da gramática inicia com o lid do símbolo não-terminal, seguido pelo caracter :, e continua com a sequência de produções. Cada produção é precedida por uma barra vertical |; a primeira barra é opcional. O significado da barra é: o símbolo não-terminal id desenvolve para qualquer uma das produções.

Produções

Uma produção especifica uma sequência de símbolos terminais e não terminais que devem ser reconhecidos, e opcionalmente atribui identificadores aos seus valores semânticos, e é seguida uma anotação %prec opcional e de uma ação semântica OCaml.
Ações semânticas
Uma ação semântica é uma porção de código OCaml que é executado por forma a atribuir um valor semântico ao símbolo não-terminal com o qual esta produção está associado. Uma ação semântica pode referir-se a valores semânticos (já computados) dos símbolos terminais ou não-terminais que aparecem na produção via identificadores do valor semântico atribuídos pela produção.

            expr:
                  ...
            
            stm:
                  IF e=expr THEN s1=stm ELSE s2=stm   { IfElse (e,s1,s2) }
                | ...
        
Neste exemplo, podemos ver que na produção do símbolo não-terminal stm é atribuído ao identificador e o valor semântico resultante do símbolo não-terminal expr, e é atribuído aos identificadores s1 e s2 o valor semântico resultante do símbolo não-terminal stm para cada um dos ramos do if. Na ação semântica desta produção, temos o construtor IfElse que recebe como parâmetros os identificadores com os valores semânticos atribuídos nessa produção.
Anotações %prec
O nível de precedência de uma produção é definida como o nível de precedência do símbolo terminal mais à direita nessa produção. No entanto, é possível definir um nível arbitrária através da uso da anotação %prec id, que indica que o nível de precedência dessa produção é o nível atribuído ao símbolo id via uma declaração %left, %right ou %nonassoc anterior. O nível de precedência atribuído a uma produção é usado para resolver conflitos shift/reduce.

            %token PLUS MINUS TIMES DIV
            %left PLUS MINUS
            %left TIMES DIV
            %nonassoc uminus
            ...
            %%

            ...

            expr:
                expr PLUS expr          {}
              | expr MINUS expr         {}
              | expr TIMES expr         {}
              | expr DIV expr           {}
              | MINUS expr %prec uminus {}
        
Aqui podemos ver que é usada anotação %prec na produção MINUS expr %prec UMINUS. Como o símbolo terminal mais à direita nesta produção é o MINUS, esta produção teria o mesmo nível de precedência que as produções expr PLUS expr e expr MINUS expr. No entanto, tratando-se da negação aritmética, é desejado que esta produção tenha um nível de precedência maior que os restantes. Para tal, definiu-se o símbolo uminus com precedência maior que os restantes símbolos e usou-se a anotação %prec uminus para definir o nível de precedência dessa produção como o mais alto.

Exemplo de uma especificação para uma linguagem aritmética:


            (* Opcional *)
            %{
                ...
            %}

            %token INT PLUS MINUS TIMES DIV EOF
            %left PLUS MINUS
            %left TIMES DIV
            %nonassoc uminus
            (* Temos então o seguinte nível de prioridades
               (do menor para o maior; tokens separados por
                vírgula têm o mesmo nível de prioridade):
               PLUS, MINUS -> TIMES, DIV -> uminus *)
            %start  main
            %%

            main:
                expr EOF  { };

            expr: INT                       { }
                | expr PLUS expr            { }
                | expr MINUS expr           { }
                | expr TIMES expr           { }
                | expr DIV expr             { }
                | MINUS expr %prec uminus   { };

            (* Opcional *)
            %%
                ...
        

Parcialmente adaptado do manual do Menhir.



Código dos exemplos

Poderá encontrar todo o código dos exemplos mostrados na aula aqui.