Description

Lex (or Flex) is a tool for generating lexical analyzers (scanners): programs that recognize lexical patterns in text. Flex reads the given input files, or its standard input if no file names are given, for a description of a scanner to be generated. The description is in the form of pairs of regular expressions and C code, called rules. Flex generates as output a C source file, lex.yy.c, which defines a routine yylex(). This file is compiled and linked with the -lfl library to produce an executable. When the executable is run, it analyzes its input for occurrences of the regular expressions. Whenever it finds one, it executes the corresponding C code.

Documentation

• Unix manual page, Html version, or PDF version.
  
• Addtional documentation, by M. E. Lesk and E. Schmidt. (very good) - newer version
• Notes on installing and using Flex (by R. Tropper, 2009) - note: this information may be outdated, please ask the TA

Edition, compilation, etc.

• To edit the files, it is recommended that you simply use the notepad.
  
• To compile the examples, open a MS-DOS Prompt (dos window) and use the commands given in comments in the source files.
  
• The compilation will produce an executable program that you can execute simply by invoking its name in the command prompt
  

Examples

• Very simple parser that count lines: parser1.lex.
  
• A little more interesting parser counting lines and characters: parser2.lex.
  
• A parser recognizing student IDs: parser3.lex.
• Example of a C program using a lex parser to get tokens: parser5, with detailed explanations on how this can be done.
  

Your tasks

1. Download, compile and experiment the examples of parsers given above. Try eventually to modify them in order to get familiar with their edition, compilation etc.
2. For several regular expressions seen in Part 1, use Lex to construct a parser that will implement the regular expression. This means that your parser will recognize words characterized by its corresponding regular expression. For instance, the parser implementing the regular expression " aa (a | b)* " will only recognize words starting with aa.
3. Construct a lexical analyser for recognizing e-mail addresses. Notes:

• Your executable should be named spamfinder
  • Note: In the Unix operating system, you can redefine the standard input and output files by calling the program in the command line using the following notation: "spamfinder < myinputfile" or "spamfinder > myoutputfile" or "spamfinder < myinputfile > myoutputfile"
• Your output file should contain one e-mail address per line. Do not insert any additional text of spaces.
• RFC2822 could be interesting to consult, but you do not have to conform to the specification in detail. Your program does not need to know the root domain names (.com, .net, .org, .ca, ...), but if you like you may get into this.
• Here are some examples of valid e-mail addresses:
  • bochmann@site.uottawa.ca
  • groupe.seg-2501@site.uottawa.ca
  • bill@microsoft.com
  • localhost@127.0.0.1
• Here are some examples of invalid e-mail addresses that should be ignored:
  • seg2501
  • seg@
  • seg@seg@qc.ca
  • groupe@.qc.ca
  • .@site.uottawa.ca
  • groupe@site..uottawa
• You do not have to eliminate multiple instances of the same address, nor sort the result.

4. Another suggestion (optional): Use Lex to program a parser implementing the following grammar:

      SENTENCE    --> NOUN_PHRASE  VERB  NOUN_PHRASE 
      VERB        --> hit
      NOUN_PHRASE --> ARTICLE   NOUN
      NOUN_PHRASE --> PROPER_NAME
      ARTICLE     --> a  |  the
      NOUN        --> ball  |  bat
      PROPER_NAME --> peter

Instructions and help for doing this lab

• How to execute (F)Lex under Unix or Windows
• Steps for doing this Lab (and suggestions for the TA) by Dr. Zhao in 2007
• Comments by Robin Tropper (TA - 2009) - note: may be outdated (from 5 years ago)