1956 Noam Chomsky comprese che
Grammars are best introduced by example.
slogan: "da stringa nasce stringa"
(Lettere di 2 tipi mutuamente esclusivi, se una lettera e' di un tipo, allora non e' dell'altro.)
es: 1: A→bA; 2: A→b da bbA→bbbA reg1; bbA→bbb reg2
La stringa in corso puo' non essere generabile poiche' procedimento:
the classic formalization of generative grammars first proposed by Noam Chomsky in the 1950s
G formal grammar le regole per generare le stringhe del suo linguaggio formale.
N e Σ hanno almeno 1 simbolo; non hanno simboli in comune, per escludere equivoco; i simboli sono indivisibili.
α must contain at least 1 nonterminal
language generated by the grammar all distinct strings that can be generated in this manner.
weak equivalence of two grammars they generate the same set of strings, i.e. they generate the same formal language.
strong (≡ structural) equivalence additionally means that the two parse trees are reasonably similar in that the same semantic interpretation can be assigned to both.
Introduced by Chomsky (1963), who argues that only strong equivalence is relevant when comparing grammar formalisms.
Grammars are best introduced by example.
ref: cs.ksu.edu/~schmidt
Two key uses of formulas are in propositional logic and predicate logic.
where the alphabet is divided into terminal and nonterminal symbols, and all inference rules are local and involve a nonterminal on the LHS. The computation starts from a specific initial nonterminal and halts when the word contains only terminals. The set of possible resulting words is the language defined by the grammar.
ref: stackexchange/relations-between-formal-systems-rewriting-systems
2: A→b la lettera A viene sostituita da b
ambiguous grammar the same string can be generated in essentially different ways.
Non esiste un procedimento generale per riscrivere una grammatica ambigua con una grammatica equivalente e non ambigua.
syntactic ambiguity ≡ structural ambiguity ≡ amphiboly ≡ amphibology
sentence may be interpreted in more than one way due to ambiguous sentence structure.
Syntactic ambiguity arises not from the range of meanings of single words (polysemy), but from the relationship between the words and clauses of a sentence, and the sentence structure underlying the word order therein. In other words, a sentence is syntactically ambiguous when a reader or listener can reasonably interpret one sentence as having more than one possible structure.
wp/Syntactic_ambiguity | Polysemy semantic ambiguity
Ambiguity#Semantic_and_syntactic_ambiguity
Scopo: da una stringa generare una nuova stringa, seguendo le regole
Regola | Stringa iniziale |
Stringa generata |
cmt |
---|---|---|---|
A → c | rBcDAbb | rBcDcbb | 1 elemento sostituibile sostituito con 1 terminale |
A → b | AAA | AbA | regola: 1 sostituzione alla volta |
Ab → cDD | rBcDAbb | rBcDcDDb | |
DAb → | rBcDAbb | rBcb | parte dx può essere vuota |
DAb → D | rBcDAbb | rBcDDb | parte dx può essere vuota |
B → cAD | rBcDAbb | rcADcDAbb | |
S → c | c | 1ª produzione | |
→ |
1ª produzione: il processo inizia indicando la regola di avvio, che agisce sulla stringa vuota; usualmente la parte sinistra e' cositituita dalla sola lettera S.
α, β stringhe di sostituibili e terminaii mischiate in qualsiasi modo e nr
α ha almeno 1 sostituibile
β puo' essere stringa_vuota
A→a, A→b, ..., A→u breve A → a|b|...|u
A→0, A→1, ..., A→9 breve A → 0|1|2|3|4|5|6|7|8|9
derivation of a string (for a grammar) a sequence of grammar rule applications that transform the start string into the string.
A derivation proves that the string belongs to the grammar's language.
wp/Derivations and syntax trees (leftmost derivation)
noncontracting_grammar in ogni regola di produzione
lunghezza parte sinistra ≤ len(parte destra)
ref: wp
Context-free grammar. Context-sensitive grammar.
LR scan left to right, using right reductions
LR(k) " " with k character of lookahead
1965: LR grammars discovered by Knuth.
LL scan left to right, using left reductions
LL(k) " " with k character of lookahead
LL(1) is important.
1968: LL grammars discovered by Lewis and Stearns.
LL_parser | LL_grammar | Leftmost derivation
LR_parser (and grammar)
Bottom-up_parsing ha disegni e confronto con Top-down_parsing
Regular_language | Regular_grammar
Deterministic_context-free_language
Deterministic_pushdown_automaton
legati da: i linguaggi accettati da tali automi
Deterministic_context-free_grammar; are unambiguos, ma non coprono tutte le grammatiche anambigue.
Automa_(informatica) | Automata_theory | Abstract_machine
Automa_a_stati_finiti | Finite-state_machine
Type | Languages | Automaton | Production rules | Examples |
---|---|---|---|---|
Ty0 | Recursively enumerable | Turing machine (TM) | γ → β | |
0.5 | Recursive | |||
Ty1 | Context-sensitive | Linear-bounded non-deterministic TM | αAβ → αγβ | L={anbncn | n>0} |
Ty2 | Context-free | Non-deterministic pushdown automaton | A → β | L={anbn | n>0} |
Ty3 | Regular | Finite state automaton | A → a A → aB |
L={an | n≥0} |
Meaning of symbols:
a = terminal α , β = maybe empty
|
left & right side of the production rule are strings
es: bcaBABad → CcB
"replace the left-side with the right-side".
Durante il processo di generazione, nella stringa attuale