Por que analisadores on-line parecem parar em regexps?

Question

Eu estive pensando por muito tempo porque não parece haver qualquer analisadores para, digamos, BNF , que se comportam como regexps em várias bibliotecas.

Claro, há coisas como ANTLR , Yacc e muitos outros que gerar o código , que, por sua vez, pode analisar uma CFG , mas não parece ser uma biblioteca que pode fazer isso sem a etapa intermediária.

Estou interessado em escrever um Packrat analisador , para arrancar todos aqueles aninhada -parenthesis-peculiaridades associadas com regexps (e, talvez ainda mais, para o esporte dele), mas de alguma forma eu tenho essa sensação de que estou apenas andando em outro problema da parada -como classe de pântanos.

Existe uma limitação técnica / teórica para esses analisadores, ou estou apenas faltando alguma coisa?

Answer 1

Eu acho que é mais uma coisa cultural. O uso de gramáticas livres de contexto está confinado a compiladores, que normalmente possuem código associado com cada regra de produção. Em alguns idiomas, é mais fácil para o código de saída do que retornos de chamada simulados. Em outros, você verá as bibliotecas do analisador: combinadores analisador em Haskell, por exemplo. Por outro lado, as expressões regulares ver ampla utilização em ferramentas como grep, onde é inconveniente para executar o compilador C cada vez que o usuário dá uma nova expressão regular.

Answer 2

Boost.Spirit parece com o que você está depois.

Se você está procurando para fazer o seu próprio, eu usei BNFC para o meu projeto mais recente do compilador e fornece a gramática usada em sua própria implementação . Este pode ser um bom ponto de partida ...

Answer 3

Não e limitação técnica / teórica à espreita nas sombras é. Eu não posso dizer por que eles não são mais populares, mas eu sei de pelo menos uma biblioteca que fornece esse tipo de "on-line" de análise que você procura.

SimpleParse é uma biblioteca python que permite que você simplesmente colar a sua gramática EBNF peludo em seu programa e usá-lo às coisas de análise imediatamente, sem degraus itermediate. Eu usei-o para diversos projetos onde eu queria uma linguagem de entrada personalizado, mas realmente não querem se comprometer com qualquer processo de construção formal.

Aqui está um pequeno exemplo em cima da minha cabeça:

decl = r"""
    root := expr
    expr := term, ("|", term)*
    term := factor+
    factor := ("(" expr ")") / [a-z]
"""
parser = Parser(decl) 
success, trees, next = parser.parse("(a(b|def)|c)def")

As bibliotecas analisador de combinadores Haskell e Scala também deixe sua expressa sua gramática para o seu analisador no mesmo pedaço de código que o utiliza. No entanto, você não pode, digamos, que o usuário digite uma gramática em tempo de execução (que só pode ser de interesse para as pessoas que fazem software para ajudar as pessoas a entender gramáticas de qualquer maneira).

Answer 4

pyparsing ( http://pyparsing.wikispaces.com ) foi construído com suporte para análise packrat e é pura Python, assim você pode ver a implementação real.

Answer 5

Porque gramáticas full-blown livres de contexto são bastante confuso como são, sem alguma sintaxe enigmaticamente densa e incompreensível para torná-los ainda mais confuso?

É difícil saber o que você está pedindo. Você está tentando criar algo como uma expressão regular, mas para gramáticas livres de contexto? Como, usando $var =~ /expr = expr + expr/ (em Perl) e tendo que "1 + 1" jogo ou "1 + 1 + 1" ou "1 + 1 + 1 + 1 + 1 + ..."? Eu acho que uma das limitações deste vai ser sintaxe:. Ter mais de cerca de três regras vai fazer a sua "gramática-expressão" ainda mais ilegível do que qualquer expressão regular moderna

Answer 6

Efeito colateral é a única coisa que eu vejo coisa que vai te pegar. A maioria dos geradores de analisador incluem código incorporado para processamento e você precisaria de um eval para fazer esse trabalho.

Uma maneira de contornar isso seria para citar ações e, em seguida, fazer uma função de "ação" que leva o nome da ação para fazer e os argumentos para fazer com ele.

Answer 7

Você poderia, teoricamente, fazê-lo com impulso Espírito em C ++, mas é principalmente para gramáticas estáticos. Penso que a razão não é comum é que CFGs não são tão comumente usado como regexs. Eu nunca tive que usar uma gramática exceto para construção de compiladores, mas eu tenho usado regexs muitas vezes. CFGs são geralmente muito mais complexo do que regexs, por isso faz sentido para gerar código estaticamente com uma ferramenta como YACC ou ANTLR.

Answer 8

tcllib tem algo assim, se você pode colocar-se com Parse Gramáticas expressão e também TCL. Se Perl é sua coisa CPAN tem Parse :: Earley . Aqui 's uma variação Perl puro que parece promissor. PLY parece ser uma solução plausível para Python