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.
View Full Document

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
View Full Document

Grammar

40 views

Other


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

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

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view Grammar and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Grammar and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?