Το μεταεργαλείο lex

Μεταεργαλεία

• Τα μεταεργαλεία είναι εργαλεία για τη δημιουργία άλλων εργαλείων.
• Παραδείγματα τέτοιων εργαλείων είναι:
  • οι μεταλεκτικοί αναλυτές (scanner generators),
  • οι μετασυντακτικοί αναλυτές (parser generators),
  • οι μεταμεταγλωττιστές (compiler generators),
  • οι δημιουργοί τέλειων συναρτήσεων κατακερματισμού (perfect hash function generators),
  • οι δημιουργοί συναρτήσεων fast fourier transform.
• Τα μεταεργαλεία αυτά δέχονται τυπικά μια δηλωτική περιγραφή του εργαλείου που θέλουμε να υλοποιήσουμε και δημιουργούν τον αντίστοιχο κώδικα.
• Προϋπόθεση για την ύπαρξη ενός τέτοιου εργαλείου είναι η ύπαρξη θεωρίας και αλγορίθμων που να οδηγεί από τη δηλωτική περιγραφή στον τελικό κώδικα.

Το μεταεργαλείο lex

• Το μεταεργαλείο lex επιτρέπει την αυτόματη δημιουργία σαρωτών κειμένου (text scanners) και κατ' επέκταση λεκτικών αναλυτών.
• Ως είσοδο δέχεται κανονικές εκφράσεις και ενέργειες .
• Ως έξοδο παράγει κώδικα σαρώνει το κείμενο εισόδου και εκτελεί τις αντίστοιχες ενέργειες ανάλογα με τις κανονικές εκφράσεις που αντιστοιχούν στο κείμενο.
• Η λειτουργία του κώδικα που παράγει βασίζεται σε αιτιοκρατικά πεπερασμένα αυτόματα.

Διαδικασία χρήσης

• Το αρχείο εισόδου για το εργαλείο lex έχει κατάληξη .l
• Το αρχείο εισόδου περιέχει δηλωτική περιγραφή της λειτουργίας του τελικού σαρωτή (κανονικές εκφράσεις και ενέργειες).
• Το εργαλείο lex διαβάζει το αρχείο αυτό και δημιουργεί ένα αρχείο σε C με όνομα lex.yy.c που υλοποιεί το σαρωτή που προδιαγράψαμε.
• Ο σαρωτής είναι υλοποιημένος στη συνάρτηση yylex().
• Η είσοδος του σαρωτή που δημιουργείται είναι το πρότυπο αρχείο εισόδου (standard input).
• Για τη λειτουργία του σαρωτή τυπικά καλούμε τη συνάρτηση yylex() μέσω της συνάρτησης main() την οποία υλοποιούμε εμείς.

Αρχείο εισόδου

• Το αρχείο εισόδου αποτελείται από τα παρακάτω τμήματα:
  • ορισμοί (definitions)
  • κανόνες (rules)
  • κώδικας χρήστη (user code)
• Η δομή του αρχείου είναι η παρακάτω:

  definitions
  %%
  rules
  %%
  user code
  

• Οι ορισμοί επιτρέπουν τον ορισμό κανονικών εκφράσεων με τη σύνταξη:

  name definition.
  

• Παράδειγμα:

  DIGIT    [0-9]
  ID       [a-z][a-z0-9]*
  

• Στους ορισμούς προσθέτουμε και την εντολή:

  %option noyywrap
  

  για να δηλώσουμε πως η είσοδός μας αποτελείται από ένα μόνο αρχείο.
• Στους ορισμούς μπορούμε να ορίσουμε και μεταβλητές της C για δική μας χρήση αρχίζοντας της γραμμή με κενό:

  DIGIT	[0-9]
  
  	int numlines;
  

• Τέλος στους ορισμούς μπορούμε να ορίσουμε πρόσθετα αρχεία εισόδου μέσα σε ενότητες %{ και %}:

  %{
  #include <math.h>
  %}
  

• Οι κανόνες ορίζουν ενέργειες που αντιστοιχούν σε κανονικές εκφράσεις (ΚΕ) της εισόδου με τη σύνταξη:

  pattern action.
  

  όπου pattern είναι μια ΚΕ και action κώδικας σε C.
• Παράδειγμα:

  ("hi")*		printf("hi or hihi or hihihi ...\n");
  DIGIT		printf("Read one digit\n");
  

• Τέλος ο κώδικας χρήστη αντιγράφεται ως έχει στον παραγόμενο κώδικα.

Κανονικές εκφράσεις

`x'

match the character `x'

`.'

any character (byte) except newline

`[xyz]'

a "character class"; in this case, the pattern matches either an `x', a `y', or a `z'

`[abj-oZ]'

a "character class" with a range in it; matches an `a', a `b', any letter from `j' through `o', or a `Z'

`[^A-Z]'

a "negated character class", i.e., any character but those in the class. In this case, any character EXCEPT an uppercase letter.

`[^A-Z\n]'

any character EXCEPT an uppercase letter or a newline

`r*'

zero or more r's, where r is any regular expression

`r+'

one or more r's

`r?'

zero or one r's (that is, "an optional r")

`r{2,5}'

anywhere from two to five r's

`r{2,}'

two or more r's

`r{4}'

exactly 4 r's

`{name}'

the expansion of the "name" definition (see above)

`"[xyz]\"foo"'

the literal string: `[xyz]"foo'

`\x'

if x is an `a', `b', `f', `n', `r', `t', or `v', then the ANSI-C interpretation of \x. Otherwise, a literal `x' (used to escape operators such as `*')

`\0'

a NUL character (ASCII code 0)

`\123'

the character with octal value 123

`\x2a'

the character with hexadecimal value 2a

`(r)'

match an r; parentheses are used to override precedence (see below)

`rs'

the regular expression r followed by the regular expression s; called "concatenation"

`r|s'

either an r or an s

`r/s'

an r but only if it is followed by an s. The text matched by s is included when determining whether this rule is the longest match, but is then returned to the input before the action is executed. So the action only sees the text matched by r. This type of pattern is called trailing context. (There are some combinations of `r/s' that flex cannot match correctly; see notes in the Deficiencies / Bugs section below regarding "dangerous trailing context".)

`^r'

an r, but only at the beginning of a line (i.e., which just starting to scan, or right after a newline has been scanned).

`r$'

an r, but only at the end of a line (i.e., just before a newline). Equivalent to "r/\n". Note that flex's notion of "newline" is exactly whatever the C compiler used to compile flex interprets '\n' as; in particular, on some DOS systems you must either filter out \r's in the input yourself, or explicitly use r/\r\n for "r$".

`<s>r'

an r, but only in start condition s (see below for discussion of start conditions) <s1,s2,s3>r same, but in any of start conditions s1, s2, or s3

`<*>r'

an r in any start condition, even an exclusive one.

`<<EOF>>'

an end-of-file <s1,s2><<EOF>> an end-of-file when in start condition s1 or s2

Τιμές προσβάσιμες στο χρήστη

• Το κείμενο της ΚΕ που αναγνώρισε το εργαλείο lex βρίσκεται πάντα στη μεταβλητή

  char *yytext;
  

• Παράδειγμα:
  %%
  [A-Z][a-z]+     printf("Found a name: %s\n", yytext);
  %%
  

Απλό παράδειγμα

Παράδειγμα χρήσης

athena:~/t> cat foo.l
%option noyywrap

        int num_lines = 0, num_chars = 0;

%%
\n      ++num_lines; ++num_chars;
.       ++num_chars;

%%
main()
        {
        yylex();
        printf( "# of lines = %d, # of chars = %d\n",
                num_lines, num_chars );
        }
athena:~/t> lex foo.l
athena:~/t> cc -o foo lex.yy.c
athena:~/t> foo <foo.l
# of lines = 15, # of chars = 261
athena:~/t>

Σύνθετο παράδειγμα

Τρόπος λειτουργίας

• Η λειτουργία του lex βασίζεται στην δημιουργία ενός ΜΠΑ από το αρχείο εισόδου.
• Στη συνέχεια το ΜΠΑ μετατρέπεται σε ΝΠΑ.
• Στο αρχείο εξόδου περιέχεται κώδικας C ο οποίος υλοποιεί τη λειτουργία του ΝΠΑ καθώς και οι αντίστοιχοι πίνακες μετάβασης.
• Για λόγους απόδοσης οι χαρακτήρες εισόδου κατανέμονται σε κλάσεις ισοδυναμίας και αυτές σε μετακλάσεις ισοδυναμίας. Με τον τρόπο αυτό περιορίζεται ο αριθμός των καταστάσεων.

Παράδειγμα

Αρχείο εισόδου

Μη αιτιοκρατικό πεπερασμένο αυτόματο

                 συμβ.   Κ1    Κ2
Κατάσταση    1	 ε :     0,    0
Κατάσταση    2	 ε :     0,    0
Κατάσταση    3	 h :     4,    0	// Διάβασε h
Κατάσταση    4	 i :     5,    0	// Διάβασε i
Κατάσταση    5	 ε :     0,    0  [1]	// Αναγνώρισε hi
Κατάσταση    6	 ε :     1,    3
Κατάσταση    7	 . :     8,    0	// Διάβασε .
Κατάσταση    8	 ε :     0,    0  [2]	// Αναγνώρισε .
Κατάσταση    9	 ε :     6,    7
Κατάσταση   10	 EOF:    11,   0
Κατάσταση   11	 ε :     0,    0  [3]	// Τέλος του αρχείου
Κατάσταση   12	 ε :     9,   10

Κλάσεις ισοδυναμίας

\000 = -1  ' ' = 1     @ = 1     ` = 1 
\001 = 1     ! = 1     A = 1     a = 1
\002 = 1     " = 1     B = 1     b = 1
\003 = 1     # = 1     C = 1     c = 1
\004 = 1     $ = 1     D = 1     d = 1
\005 = 1     % = 1     E = 1     e = 1
\006 = 1     & = 1     F = 1     f = 1
  \a = 1     ' = 1     G = 1     g = 1
  \b = 1     ( = 1     H = 1     h = 3
  \t = 1     ) = 1     I = 1     i = 4
  \n = 1     * = 1     J = 1     j = 1
  \v = 1     + = 1     K = 1     k = 1
  \f = 1     , = 1     L = 1     l = 1
  \r = 1     - = 1     M = 1     m = 1
\016 = 1     . = 2     N = 1     n = 1
\017 = 1     / = 1     O = 1     o = 1
\020 = 1     0 = 1     P = 1     p = 1
\021 = 1     1 = 1     Q = 1     q = 1
\022 = 1     2 = 1     R = 1     r = 1
\023 = 1     3 = 1     S = 1     s = 1
\024 = 1     4 = 1     T = 1     t = 1
\025 = 1     5 = 1     U = 1     u = 1
\026 = 1     6 = 1     V = 1     v = 1
\027 = 1     7 = 1     W = 1     w = 1
\030 = 1     8 = 1     X = 1     x = 1
\031 = 1     9 = 1     Y = 1     y = 1
\032 = 1     : = 1     Z = 1     z = 1
\033 = 1     ; = 1     [ = 1     { = 1
\034 = 1     < = 1     \ = 1     | = 1
\035 = 1     = = 1     ] = 1     } = 1
\036 = 1     > = 1     ^ = 1     ~ = 1
\037 = 1     ? = 1     _ = 1  \177 = 1 

Μετακλάσεις ισοδυναμίας

1 = 1
2 = 1
3 = 1
4 = 2

Αιτιοκρατικό πεπερασμένο αυτόματο

Κατάσταση # 1:
	1	4
	2	5	// .
	3	6	// h
	4	4
Κατάσταση # 2:
	1	4
	2	5	// .
	3	6	// h
	4	4
Κατάσταση # 3:
Κατάσταση # 4:
Κατάσταση # 5:		// Αναγνώρισε .
Κατάσταση # 6:
	4	7	// i
Κατάσταση # 7:		// Αναγνώρισε hi

Παραγόμενος κώδικας σε C (τμήματα)

Ασκήσεις

1. Να υλοποιήσετε με το μεταεργαλείο lex έναν λεκτικό αναλυτή που να αναγνωρίζει τα παρακάτω λεκτικά σύμβολα:
   • ακέραιοι
   • μεταβλητές (όπως της C)
   • δεσμευμένη λέξη if
   • δεσμευμένη λέξη else
   • δεσμευμένη λέξη while
   • δεσμευμένη λέξη for
   • δεσμευμένη λέξη switch
   • δεσμευμένη λέξη case
   Ο λεκτικός αναλυτής θα τυπώνει στην έξοδό του τον τύπο του κάθε συμβόλου που θα αναγνωρίζει καθώς και την τιμή του. Παράδειγμα:

   Read integer (42)
   Read variable (i)
   Read keyword (while)
   

Βιβλιογραφία

• Εμμ. Σ. Σκορδαλάκης. Εισαγωγή στους Μεταγλωττιστές σ. 224-234. Συμμετρία 1993.

• Free Software Foundation. Flex - a scanner generator. Available online: http://www.gnu.org/manual/flex-2.5.4/flex.html, November 1998.
• Michael E. Lesk. Lex — a lexical analyzer generator. Computer Science Technical Report 39, Bell Laboratories, Murray Hill, NJ, USA, October 1975.
• John Levine, Tony Mason, and Doug Brown. Lex and Yacc. O'Reilly & Associates, second edition, 1992.

• Περιεχόμενα

 Τελευταία αλλαγή: Τρίτη, 19 Σεπτεμβρίου 2006 6:27 μμ
 Εκτός αν αναφέρεται κάτι διαφορετικό, όλο το πρωτότυπο υλικό της σελίδας αυτής του οποίου δημιουργός είναι ο Διομήδης Σπινέλλης παρέχεται σύμφωνα με τους όρους της άδειας «Creative Commons Attribution-Share Alike 3.0 Greece License».