Formal Languages and Compilers Exam 2 Terms

Context Free Grammar

A formal grammar whose production rules can be applied to non-terminal symbols regardless of the context.

Formal grammar

set of production rules that define the set of strings in the language

Production rules

rules to write strings using terminal and non-terminal characters

terminal symbol

a symbol that belongs to the alhpabet of the language

non-terminal symbol

a symbol that does not belong to the language

A CFL is the language L(G) __________________

Derived from a context free grammar G

CFG G=(_________)

V, E, S, P where v= finite set of non terminal chars E= finite set of terminal characters S=start symbol P=production rules

CFLs are closed under what

Union, concatenation, and Kleene star

all regular languages are ________

context free

A language is regular when_________________

there exists a regular grammar for it

what defines ambiguity

A CFG is ambiguous if there is at least one string in the language that has two or more derivation trees

How is ambiguity handled

Not all grammars can be made unambiguous. YACC can handle ambiguous grammars.

PDA

Machine that determines if the rules of a are being followed by and example text.

The Stack

A form of memory for the pda