Parser/Grammer: 2x parenthesis in nested rules
Despite my limited knowledge about compiling/parsing I dared to build a small recursive descent parser for OData $filter expressions. The parser only needs to check the expression for correctness and output a corresponding condition in SQL. As input and output have almost the same tokens and structure this was fairly straightforward and my implementation does 90% of what I want.
But now I got stuck with parenthesis, which appear in separate rules for logical and arithmetic expressions. The full OData grammar in ABNF is here, a condensed version of the rules involved is this:
boolCommonExpr = ( boolMethodCallExpr
/ notExpr
/ commonExpr [ eqExpr / neExpr / ltExpr / ... ]
/ boolParenExpr
) [ andExpr / orExpr ]
commonExpr = ( primitiveLiteral
/ firstMemberExpr ; = identifier
/ methodCallExpr
/ parenExpr
) [ addExpr / subExpr / mulExpr / divExpr / modExpr ]
boolParenExpr = "(" boolCommonExpr ")"
parenExpr = "(" commonExpr ")"
Como essa gramática corresponde a uma expressão simples como (1 eq 2)? Pelo que pude perceber todos (são consumidos pela regra parenExprinterna commonExpr, ou seja, também devem fechar depois commonExprpara não causar erro e boolParenExprnunca serem atingidos. Suponho que minha experiência / intuição ao ler tal gramática seja insuficiente para entendê-la. Um comentário no ABNF diz: "Observe que boolCommonExpr também é commonExpr". Talvez isso seja parte do mistério?
Obviamente, uma abertura por (si só não me dirá onde vai se fechar: depois da commonExprexpressão atual ou mais longe depois boolCommonExpr. Meu lexer tem uma lista de todos os tokens à frente (URL é uma entrada muito curta). Eu estava pensando em usar isso para descobrir que tipo de (eu tenho. Boa ideia?
I'd rather have restrictions in input or a little hack than switching to a generally more powerful parser model. For a simple expression translation like this I also want to avoid compiler tools.
Edit 1: Extension after answer by rici - Is grammar rewrite correct?
Actually I started out with the example for recursive descend parsers given on Wikipedia. Then I though to better adapt to the official grammar given by the OData standard to be more "conformant". But with the advice from rici (and the comment from "Internal Server Error") to rewrite the grammar I would tend to go back to the more comprehensible structure provided on Wikipedia. Adapted to the boolean expression for the OData $filter this could maybe look like this:
boolSequence= boolExpr {("and"|"or") boolExpr} .
boolExpr = ["not"] expression ("eq"|"ne"|"lt"|"gt"|"lt"|"le") expression .
expression = term {("add"|"sum") term} .
term = factor {("mul"|"div"|"mod") factor} .
factor = IDENT | methodCall | LITERAL | "(" boolSequence")" .
methodCall = METHODNAME "(" [ expression {"," expression} ] ")" .
O acima faz sentido em geral para expressões booleanas, é basicamente equivalente à estrutura original acima e digerível para um analisador descendente recursivo?
@rici: Obrigado por seus comentários detalhados sobre a verificação de tipo. A nova gramática deve resolver suas preocupações sobre a precedência em expressões aritméticas.
Para todos os três terminais (MAIÚSCULAS na gramática acima) meu lexer fornece um tipo (string, número, data / hora ou booleano). Não terminais retornam o tipo que produzem. Com isso, consegui fazer a verificação de tipo em tempo real em minha implementação atual, incluindo mensagens de erro decentes. Esperançosamente, isso também funcionará para a nova gramática.
Edição 2: Retorne à gramática OData original
A diferenciação entre "lógico" e "aritmético" (não é trivial. Para resolver o problema, até N.Wirth usa uma solução alternativa duvidosa para manter a gramática de Pascal simples. Como consequência, em Pascal um par extra de () é ao redor e expressões obrigatórias . Nem intuitivo nem compatível com OData :-(. A melhor leitura sobre a "dificuldade ()" que encontrei está em Let's Build a Compiler (Parte VI) . Outras linguagens parecem exigir muito da gramática para resolver o problema. Como não tenho experiência com construção gramatical, parei de fazer a minha.andor
Acabei implementando a gramática OData original. Antes de executar o analisador, repasso todos os tokens para descobrir quais (pertencem a uma expressão lógica / aritmética. Não é um problema para o comprimento potencial de um URL.
Respostas
Pessoalmente, eu apenas modificaria a gramática para que tenha apenas um tipo de expressão e, portanto, um tipo de parêntese. Não estou convencido de que a gramática OData esteja realmente correta; certamente não é utilizável em um analisador LL (1) (ou descida recursiva) exatamente pelo motivo que você mencionou.
Especificamente, se o objetivo for boolCommonExpr, há duas produções que podem corresponder ao (token de lookahead:
boolCommonExpr = ( …
/ commonExpr [ eqExpr / neExpr / … ]
/ boolParenExpr
/ …
) …
commonExpr = ( …
/ parenExpr
/ …
) …
Para a maior parte, essa é uma tentativa equivocada de fazer a gramática detectar uma violação de tipo. (Se de fato for uma violação de tipo.) É equivocado porque está fadado ao fracasso se houver variáveis booleanas, que aparentemente existem neste ambiente. Uma vez que não há nenhuma pista sintática quanto ao tipo de uma variável, o analisador não é capaz de decidir se expressões particulares são bem formadas ou não, então há um bom argumento para não tentar de jeito nenhum, especialmente se isso criar dores de cabeça na análise. Uma solução melhor é primeiro analisar a expressão em um AST de alguma forma e, em seguida, fazer outra passagem sobre o AST para verificar se cada operador tem operandos do tipo correto (e possivelmente inserir operadores de conversão explícitos, se necessário).
Além de qualquer outra vantagem, fazer a verificação de tipo em uma passagem separada permite produzir mensagens de erro muito melhores. Se você cometer (alguns) erros de sintaxe de violação de tipo, poderá deixar o usuário intrigado sobre o motivo de sua expressão ter sido rejeitada; em contraste, se você notar que uma operação de comparação está sendo usada como um operando para se multiplicar (e se a semântica do seu idioma não permitir uma conversão automática de Verdadeiro / Falso para 1/0), você pode produzir um erro bem direcionado mensagem ("as comparações não podem ser usadas como operando de um operador aritmético", por exemplo).
Uma possível razão para colocar diferentes operadores (mas não parênteses) em diferentes variáveis gramaticais é expressar a precedência gramatical. Essa consideração pode encorajá-lo a reescrever a gramática com precedência explícita. (Conforme escrito, a gramática assume que todos os operadores aritméticos têm a mesma precedência, o que presumivelmente levaria a 2 + 3 * aser analisado como (2 + 3) * a, o que pode ser uma grande surpresa.) Alternativamente, você pode usar algum subparser ciente de precedência simples para expressões.
If you want to test your ABNF grammar for determinism (i.e. LL(1)), you can use Tunnel Grammar Studio (TGS). I have tested the full grammar, and there are plenty of conflicts, not only this scopes. If you are able to extract the relevant rules, you can use the desktop version of TGS to visualize the conflicts (the online version checker is with a textual result only). If the rules are not too many, the demo may help you to create an LL(1) grammar from your rules.
If you extract all rules you need, and add them to your question, I can run it for you and will tell you is it LL(1). Note that the grammar is not exactly in ABNF meta syntax, because the case sensitivity is typed with ' for case sensitive strings. The ABNF (RFC 5234) by definition is case insensitive, as RFC 7405 defines the sensitivity with %s and %i (sensitive and insensitive) prefixes before the the actual string. The default case (without a prefix) still means insensitive. This means that you have to replace this invalid '...' strings with %s"..." before testing in TGS.
TGS is a project I work on.