Grammars Flashcards
What is a language?
A sequence of symbols
What is a grammar?
A set of formal rules that define what a valid sentence looks like
What is a parser?
Machines for taking a sentence in a language and deciding whether or not it adheres to the grammar, possibly performing actions on the way
What is the syntax of a language?
How languages/code is meant to be formed, not what they mean
Why are grammars important?
Almost all computer systems need to represent complex structured data, so storing and reading such data is a core task for a huge range of computer systems
What characteristics are looked at to check a sentence
- What symbols we can see
- Their ordering
- How they can be combined
What does each rule describe?
A pattern against which we match the input string, in terms of literals and other patterns
What are the two elements of context free grammars?
- Non terminals (patterns to match)
- Terminals (symbols that actually appear in the input string)
Describe the 4 tuple of a CFG
N - set of non terminals
T - set of terminals
P - set of productions mapping a non terminal to a sequence of non terminals and terminals
N0 - the initial non terminal
What is a derivation?
A particular sequence of production applications that yields a string in the language
What is a parse tree?
Each production expands to a small tree, the leaves of which are terminals
What is on the LHS and RHS of productions in a CFG?
LHS - a single non terminal
RHS - a sequence of terminals and non-terminals
What does it refer to by a context free grammar?
Refers to the way that we can always replace a non terminal in a string with the RHS of a corresponding production
What is an empty production?
A production that generates no output
What will happen if a grammar is ambiguous?
Any valid sentence will have more than one possible parse tree
