Ciência da Computação livro de texto maneira de fazer text / xml / whatever parsing

Question

Tem sido ratling no meu cérebro por um tempo.

Eu tive alguma investigação sobre Compiladores / Flex / Byson e outras coisas, mas eu nunca encontrei uma referência bem que falou em detalhes sobre a "pilha de análise sintática", ou como ir sobre a implementação de um.

Alguém sabe de boas referências onde eu poderia pegar?

Editar : Eu aprecio todas as referências do compilador, e eu estou indo para obter alguns dos livros listados, mas meu foco principal era na própria análise e não o que você faz com ele depois .

Answer 1

Esta é em resposta a resposta de Dima que você aceita como a resposta correta. Embora não seja uma má resposta a afirmar que a análise está relacionada com autômatos teoria, eu sinto que há algum mal-entendido aqui.

• Em primeiro lugar, de estado finito autômatos só são capazes de reconhecer linguagens regulares (por exemplo, expressões regulares). A fim de reconhecer linguagens livres de contexto que você precisa pushdown automata , que é mais poderoso. Consulte http://en.wikipedia.org/wiki/Automata_theory#Classes_of_automata para mais autômatos e sua relação com diferentes classes de idiomas.

• Em segundo lugar, parsing é diferente de reconhecendo . Reconhecendo uma cadeia apenas informa se essa seqüência está na linguagem gerada por sua gramática. O propósito de um analisador é produzir uma árvore de sintaxe concreta que é tanto mais difícil e geralmente mais útil.

Há uma grande variedade de analisar métodos lá fora, por isso é difícil dar-lhe uma referência específica que lhe dirá o que você precisa saber ... Em geral, você deve entender a diferença entre top-down análise e bottom-up análise. Mas aqui está uma visão geral de algumas técnicas comuns empregadas pelos geradores de analisador no caso de você estiver interessado:

• Os artigos da Wikipédia para LR Análise , LL Análise , SLR Análise , LALR Análise , GLR Análise
• O ANTLR LL (*) parsing
• Monádico Parsing em Haskell (para a construção de analisadores na programação funcional línguas)
• E o mais exótico análise da expressão Gramáticas

EDIT: Sinto muito por esbarrar esta pergunta novamente, eu só aconteceu em dois excelentes mensagens descrevendo a relação entre linguagens regulares e finito autômatos , linguagens livres de contexto e empurre-down autômatos . Pode ser interessante para as pessoas que encontrar esta questão.

Answer 2

O Dragão livro ! Usei-o há pouco tempo para escrever um compilador (em PHP!) Para uma linguagem de processamento de arquivos de modelo escritos em RTF ...

Answer 3

Um analisador é basicamente uma máquina de estado finito, também conhecido como um finito autômato. Você deve encontrar um livro sobre teoria da computação, que discute autômatos finitos, e coisas como linguagens regulares, linguagem livre de contexto, etc.

Answer 4

amazon

Compiler Construção é apenas um exemplo bom

Answer 5

Confira "Brinch Hansen on Pascal Compilers" .. ele foi escrito em 1985, mas eu usei no ano passado para um curso sobre compiladores (por Per Brinch Hansen é claro.) E achei muito conciso e útil para o projeto do compilador.