Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Grammars3-21-2011Opening DiscussionHow 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 LanguagesToday 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 GrammarsNoam Chomsky developed a hierarchy of grammar types that could be used to specify different languages.RegularContext-FreeContext-SensitiveRecursively EnumerableEach of these can also be associated with a different type of machine or automaton.Nature of Chomsky GrammarsChomsky 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 GrammarsThe simplest Chomsky grammar type is the regular grammars. There are only two types of allowed rules:A → aA → aBNote that 'A' and 'B' represent any non-terminals and 'a' is any terminal.Equivalent to a finite state automaton. Have no memory.Context-Free GrammarsAllow 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 GrammarsTakes 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 GrammarsAllows 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 ExpressionsOne 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 EssayQuestions?There is an IcP next
View Full Document