# DePaul CSC 447 - Grammar (131 pages)

Previewing pages*1, 2, 3, 4, 5, 6, 7, 8, 9, 61, 62, 63, 64, 65, 66, 67, 68, 123, 124, 125, 126, 127, 128, 129, 130, 131*of 131 page document

**View the full content.**## Grammar

Previewing pages *1, 2, 3, 4, 5, 6, 7, 8, 9, 61, 62, 63, 64, 65, 66, 67, 68, 123, 124, 125, 126, 127, 128, 129, 130, 131*
of
actual document.

**View the full content.**View Full Document

## Grammar

0 0 40 views

Other

- Pages:
- 131
- School:
- DePaul University
- Course:
- Csc 447 - Concepts of Programming Languages

**Unformatted text preview: **

Introduction to Languages and Grammars Alphabets and Languages An alphabet is a finite non empty set Let S and T be alphabets S T s t s S t T We ll often write ST for S T empty string string of length one S0 S1 S Sn S n 1 S n 1 S S1 U S2 U S3 U S S0 U S A language L over an alphabet S is a subset of S How Many Languages Are There How many languages over a particular alphabet are there Uncountably infinitely many Then any finite method of describing languages can not include all of them Formal language theory gives us techniques for defining some languages over an alphabet Why should I care about Concepts of syntax and semantics used widely in computer science Basic compiler functions Development of computer languages Exploring the capabilities and limitations of algorithmic problem solving Methods for Defining Languages Grammar Rules for defining which strings over an alphabet are in a particular language Automaton plural is automata A mathematical model of a computer which can determine whether a particular string is in the language Definition of a Grammar A grammar G is a 4 tuple G N P S where N is an alphabet of nonterminal symbols is an alphabet of terminal symbols N and are disjoint S is an element of N S is the start symbol or initial symbol of the grammar P is a set of productions of the form where is in N U N N U is in N U Definition of a Language Generated by a Grammar We define by if is in P and and are in N U is the transitive closure of is the reflexive transitive closure of The language L generated by grammar G N P S is defined by L L G x S x and x is in Classes of Grammars The Chomsky Hierarchy Type 0 Phrase Structure same as basic grammar definition Type 1 Context Sensitive 1 where is in N U N N U is in N U and length length 2 A where A is in N is in N U and and are in N U Type 2 Context Free A where A is in N is in N U Linear A x or A x B y where A and B are in N and x and y are in Type 3 Regular Expressions 1 left linear A B a or A a where A and B

View Full Document