Grammar?

Formal Definition of a Grammar

Grammar specifies the legal syntax of a language. A grammar specifies a set of productions; non-terminal symbols. A grammar describes the structure of the sentences of a language in terms of components or phrases. The mathematical description of phrase structure grammars is due to Chomsky.
문법은 언어의 syntax(the rules by which legitimate statements can be constructed)를 나타내는 규칙이다. 문법은 production으로 이루어져 있다.

Formally, a Grammar is a four-tuple G = (T, N, S, P) where:

• T is the set of terminal symbols or words of the language.
• N is the set of nonterminal symbols or phrase names that are used in specifying the grammar. We say V = T $\cup$ N is the vocabulary of the grammar.
• S is a distinguished element of N called the start symbol.
• P is a set of productions, P $\subseteq V^NV^ \texttimes V^*$. We write productions in the form a $\textrightarrow$ b where a is a string of symbols from V containing at lest one nonterminal and b is any string of symbols from V.
• V = Vocabulrary
  문법은 언어의 구조가 올바른지를 판단하는 거다.

Chart about Grammar Classes.

• General Phrase-structure
• Context Sensitive
• Context Free pushdown stack O($n^3$)
• Regular finite storage O(n)
  We’ll focus on Context-Free and Regular Language.

Regular Languages

Grammar definitions

A - xB.
A - x.
A, B $\in$ N
x $\in T^*$
Only one nonterminal can appear in any derived string, and it must appear at the rightmost.

Uses

In compilers, we use to parse the stream of characters into tokens. Cause parser never has to back up or do search. O(n); Linear parsing time. Indentifiers, numbers, word forms.

Local Ambiguity

Examples

A - xB
B - x

Way to Handle

Make test cases to pre-process it.

Relationship of finite automata and regular grammars

Equivalent to a deterministic finite automaton

Linear nature of a derivation from a regular grammar

Since only one nonterminal can appear in any derived string, and the rightmost end, parse tree has only one step to evaluate it, produces right-biased tree.

Citation:

• Aho, Lam, Sethi, & Ullman, Compilers: Principles, Techniques, and Tools
• UT Austin CS375: Compilers by G.Novak.