Chomsky Hierarchy e LL (*) parser

Question

Voglio analizzare un linguaggio di programmazione. Ho letto molto sui linguaggi formali e sulla gerarchia di Chomsky e ANTLR. Ma non sono riuscito a trovare informazioni su come correlare le lingue ANTLR v3 come un parser di discendenza ricorsiva LL (*) accetta alla gerarchia chomsky.

In che modo i tipi di Chomsky si mescolano con LL (*)? Qualsiasi informazione (online, libri, documenti) è molto apprezzata.

Modifica: in che modo i predicati sintattici / semantici e il backtracking della mappa ANTLR vengono mappati in questo?

Answer 1

La Gerarchia di Chomsky è fondamentalmente:

1. Lingue normali
2. Grammatiche senza contesto
3. Grammatiche sensibili al contesto
4. Grammatiche enumerabili in modo ricorsivo (Turing-complete)

LL Grammars (e parser) sono un sottoinsieme di grammatiche senza contesto. Vengono utilizzati perché i linguaggi regolari sono troppo deboli ai fini della programmazione e perché un parser generale privo di contesto è O (n ^ 3) che è troppo lento per l'analisi di un programma. In effetti, aumentare un parser con le funzioni di aiuto lo rende più forte. La voce di Wikipedia sui parser LL spiega alcuni di questi. The Dragon Book è considerato un libro di testo di punta sui compilatori e può spiegare ulteriormente.

Answer 2

LL (*) è un sottoinsieme di linguaggi senza contesto. Tuttavia, una domanda diversa è quale antlr può analizzare, dati i predicati e il backtracking, che ne estendono le capacità.

Nota che se parliamo di LL (*), ciò significa ANTLR v3, non 2.