1 { 2 Construct the position table, as well as first position sets. 3 4 The position table stores symbol positions in regular expressions of 5 the Lex grammar. It also allows to store the corresponding first 6 and follow sets. By this means, the position table represents an eps- 7 free nondeterministic automaton for the regular expressions of the 8 Lex grammar (cf. Aho/Sethi/Ullman, Compilers : Principles, Techniques 9 and Tools, 1986, Section 3.9, on constructing NFA's from regular 10 expressions using position tables). 11 12 13 Copyright (c) 1990-92 Albert Graef <ag@muwiinfa.geschichte.uni-mainz.de> 14 Copyright (C) 1996 Berend de Boer <berend@pobox.com> 15 16 This program is free software; you can redistribute it and/or modify 17 it under the terms of the GNU General Public License as published by 18 the Free Software Foundation; either version 2 of the License, or 19 (at your option) any later version. 20 21 This program is distributed in the hope that it will be useful, 22 but WITHOUT ANY WARRANTY; without even the implied warranty of 23 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 24 GNU General Public License for more details. 25 26 You should have received a copy of the GNU General Public License 27 along with this program; if not, write to the Free Software 28 Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA. 29 30 31 $Revision: 1.2 $ 32 $Modtime: 96-08-01 6:30 $ 33 34 $History: LEXPOS.PAS $ 35 * 36 * ***************** Version 2 ***************** 37 * User: Berend Date: 96-10-10 Time: 21:16 38 * Updated in $/Lex and Yacc/tply 39 * Updated for protected mode, windows and Delphi 1.X and 2.X. 40 41 } 42 43 44 unit LexPos; 45 46 47 interface 48 49 uses LexBase, LexTable; 50 51 52 procedure addExpr(r : RegExpr; var FIRST : IntSet); 53 (* Add the positions in r to the position table, and return the set of 54 first positions of r. *) 55 56 implementation 57 58 procedure eval(r : RegExpr; 59 var FIRST, LAST : IntSet; 60 var nullable : Boolean); 61 (* Evaluates the expression r, adding the positions in r to the position 62 table and assigning FIRST, LAST and FOLLOW sets accordingly (cf. Aho/ 63 Sethi/Ullman, Compilers : Principles, Techniques and Tools, Section 3.9). 64 Returns: 65 - FIRST: the set of first positions in r 66 - LAST: the set of last positions in r 67 - nullable: denotes whether the r is nullable (i.e. is matched by the 68 empty string). *) 69 var 70 c : Char; 71 str : StrPtr; 72 cc : CClassPtr; 73 rule, pos : Integer; 74 r1, r2 : RegExpr; 75 FIRST1, LAST1 : IntSet; 76 nullable1 : Boolean; 77 i : integer; 78 begin 79 if is_epsExpr(r) then 80 begin 81 empty(FIRST); empty(LAST); 82 nullable := true 83 end 84 else if is_markExpr(r, rule, pos) then 85 begin 86 addMarkPos(rule, pos); 87 singleton(FIRST, n_pos); singleton(LAST, n_pos); 88 nullable := true 89 end 90 else if is_charExpr(r, c) then 91 begin 92 addCharPos(c); 93 singleton(FIRST, n_pos); singleton(LAST, n_pos); 94 nullable := false 95 end 96 else if is_strExpr(r, str) then 97 if length(str^)=0 then 98 (* empty string is treated as empty expression *) 99 begin 100 empty(FIRST); empty(LAST); 101 nullable := true 102 end 103 else 104 begin 105 addCharPos(str^[1]); 106 singleton(FIRST, n_pos); 107 for i := 2 to length(str^) do 108 begin 109 addCharPos(str^[i]); 110 singleton(pos_table^[pred(n_pos)].follow_pos^, n_pos); 111 end; 112 singleton(LAST, n_pos); 113 nullable := false 114 end 115 else if is_CClassExpr(r, cc) then 116 begin 117 addCClassPos(cc); 118 singleton(FIRST, n_pos); singleton(LAST, n_pos); 119 nullable := false 120 end 121 else if is_starExpr(r, r1) then 122 begin 123 eval(r1, FIRST, LAST, nullable); 124 for i := 1 to size(LAST) do 125 setunion(pos_table^[LAST[i]].follow_pos^, FIRST); 126 nullable := true 127 end 128 else if is_plusExpr(r, r1) then 129 begin 130 eval(r1, FIRST, LAST, nullable); 131 for i := 1 to size(LAST) do 132 setunion(pos_table^[LAST[i]].follow_pos^, FIRST); 133 end 134 else if is_optExpr(r, r1) then 135 begin 136 eval(r1, FIRST, LAST, nullable); 137 nullable := true 138 end 139 else if is_catExpr(r, r1, r2) then 140 begin 141 eval(r1, FIRST, LAST1, nullable); 142 eval(r2, FIRST1, LAST, nullable1); 143 for i := 1 to size(LAST1) do 144 setunion(pos_table^[LAST1[i]].follow_pos^, FIRST1); 145 if nullable then setunion(FIRST, FIRST1); 146 if nullable1 then setunion(LAST, LAST1); 147 nullable := nullable and nullable1 148 end 149 else if is_altExpr(r, r1, r2) then 150 begin 151 eval(r1, FIRST, LAST, nullable); 152 eval(r2, FIRST1, LAST1, nullable1); 153 setunion(FIRST, FIRST1); 154 setunion(LAST, LAST1); 155 nullable := nullable or nullable1 156 end 157 end(*eval*); 158 159 procedure addExpr(r : RegExpr; var FIRST : IntSet); 160 var LAST : IntSet; 161 nullable : Boolean; 162 begin 163 eval(r, FIRST, LAST, nullable); 164 end(*addExpr*); 165 166 end(*LexPos*). 167