Homework 1

Due on Thursday February 17 before midnight


This homework must be done individually. No copying is permitted.

  1. (10 points) Write a regular expression for identifiers consisting of letters, digits, the undersore character '_', and starting with a lowercase letter or the undersore character '_'.

  2. (30 points) Consider the following grammar:
    E ← id
     | id ( L )
     | id ( )
     | E . id
     | E + E
    L ← L , E
     | E
    where id is an identifier. Show that the grammar is ambiguous by drawing two different parse trees for the sentence:

  3. (40 points) Convert the grammar of Problem 2 using left recursion elimination and left factoring. (That is, rewrite the grammar in such as way that is ready for predictive parsing.)

  4. (20 points) Convert the following EBNF to BNF.
    S ← E { + E }
    E ← id [ ( E { , E } ) ]

What to Submit

Use the form below to submit your homework. We do not accept email or hardcopy submissions. You need a username and password to submit your homework. You should have already received an email from your instructor at your mavs.uta.edu account with your username and password. Use this username/password to login at the login/status web page, which is also accessible from the course web page. When you try to login the first time on Internet Explorer, you may get the error: "There is a problem with this website's security certificate" or " Content was blocked because it was not signed by a valid security certificate"; you should click for options and select: "Display Blocked Content" or "Continue to this website". Acceptable file formats for your submitted file are: plain text, Microsoft Word document (.doc), PDF (.pdf), and postscript (.ps). You may use any file name. Don't forget to put your name and student ID on your homework. You may submit your file as many times as you like, but only the most recently submitted file will be retained and evaluated.

Submit this file:

Last modified: 02/08/11 by Leonidas Fegaras