DOC PREVIEW
TRINITY CSCI 1321 - Lecture Notes

This preview shows page 1-2-3-4 out of 11 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Grammars3-21-2011Opening DiscussionHow many of you have used regular expressions before?Please do come talk to me about assignments of send me e-mails. You are still the experimental group. I need to figure out what has to change for the future.Formal LanguagesToday we will introduce the concept of formal languages and grammars.These are formal sets of rules for building strings. The rules determine what strings are in a particular language.There are many ways of specifying languages. We will focus on the one that is most broadly used today.Chomsky GrammarsNoam Chomsky developed a hierarchy of grammar types that could be used to specify different languages.RegularContext-FreeContext-SensitiveRecursively EnumerableEach of these can also be associated with a different type of machine or automaton.Nature of Chomsky GrammarsChomsky grammars have terminals and non-terminals. Normally a terminal is lowercase and a non-terminal is uppercase.There is a special non-terminal called the start symbol, S.A string in “complete” when it contains only terminals.Rules specify what a non-terminal can be replaced with.Regular GrammarsThe simplest Chomsky grammar type is the regular grammars. There are only two types of allowed rules:A → aA → aBNote that 'A' and 'B' represent any non-terminals and 'a' is any terminal.Equivalent to a finite state automaton. Have no memory.Context-Free GrammarsAllow more general rules:A → γWhere γ is any combination of terminals and non-terminals.Equivalent to a pushdown automaton. Has memory, but only as a stack.These are how we specify the syntax of programming languages. Can describe almost all natural language.Context-Sensitive GrammarsTakes surrounding characters into account:αAβ → αγβEquivalent to a linear bounded non-determinstic Turing machine.Not used all that much because of challenges. Needed for some elements of natural language.Recursively Enumerable GrammarsAllows basically any transformation.α → βThere are no bounds on what these can be.This is equivalent to a Turing machine. That means that you could calculate anything you want using one of these.Regular ExpressionsOne if the applications of these formal systems is the use of regular expressions to perform String operations.Scala has a class called scala.util.matching.Regex. You can get one of these by calling the r method on a String.This wraps the functionality of java.util.regex.Pattern and provides Scala style functionality and pattern matching.Let's look at API entries.Minute EssayQuestions?There is an IcP next


View Full Document

TRINITY CSCI 1321 - Lecture Notes

Documents in this Course
Recursion

Recursion

11 pages

Iterators

Iterators

10 pages

Actors

Actors

9 pages

Recursion

Recursion

15 pages

Recursion

Recursion

10 pages

Threads

Threads

7 pages

Trees

Trees

11 pages

Load more
Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes 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 Lecture Notes 2 2 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?