Flex (lexikal analysatorgenerator)

böja
Utvecklare	Vern Paxson
Initial release	omkring 1987 ; 36 år sedan
Stabil frisättning	2.6.4 / 6 maj 2017 ; 5 år sedan
Förvar	github .com /westes /flex .git ;
Operativ system	Unix-liknande
Typ	Generator för lexikal analys
Licens	BSD-licens
Hemsida	github .com /westes /flex

Flex (snabb lexical analyzer generator) är ett gratis och öppen källkodsmjukvarualternativ till lex . Det är ett datorprogram som genererar lexikalanalysatorer (även känd som "scanners" eller "lexers"). Den används ofta som lex-implementering tillsammans med Berkeley Yacc- parsergenerator på BSD -härledda operativsystem (eftersom både lex och yacc är en del av POSIX ), eller tillsammans med GNU bison (en version av yacc ) i *BSD-portar och i Linux distributioner. Till skillnad från Bison är flex inte en del av GNU-projektet och släpps inte under GNU General Public License , även om en manual för Flex producerades och publicerades av Free Software Foundation.

Historia

Flex skrevs i C omkring 1987 av Vern Paxson , med hjälp av många idéer och mycket inspiration från Van Jacobson . Originalversion av Jef Poskanzer . Den snabba tabellrepresentationen är en partiell implementering av en design gjord av Van Jacobson. Implementeringen gjordes av Kevin Gong och Vern Paxson.

Exempel på lexikal analysator

Detta är ett exempel på en Flex-skanner för instruktionsprogrammeringsspråket PL/0 .

De tokens som identifieras är: ' + ', ' - ', ' * ', ' / ', ' = ', ' ( ', ' ) ', ' , ', ' ; ',' . ', ' := ', ' < ', ' <= ', ' <> ', ' > ', ' >= '; siffror: 0-9 {0-9} ; identifierare: a-zA-Z {a-zA-Z0-9} och nyckelord: start , call , const , do , end , if , odd , procedure , then , var , while .


 


         
        


                           
                          
                          
                          
                         
                         
                      
                          
                         
                       
                            
                           
                            
                            
                           
                           
                   
                     
                   
                         
                       
                         
                       
                
                     
                       
                   
 
                         
                              
                
                             
             
                     0
                            


   %  {  #include  "y.tab.h"  %  }  siffra  [  0-9  ]  bokstaven  [  a  -  zA  -  Z  ]  %%  "+"  {  return  PLUS  ;  }  "-"  {  return  MINUS  ;  }  "*"  {  return  TIMES  ;  }  "/"  {  return  SLASH  ;  }  "("  {  return  LPAREN  ;  }  ")"  {  return  RPAREN  ;  }  ";"  {  return  SEMICOLON  ;  }  ","  {  return  COMMA  ;  }  "."  {  return  PERIOD  ;  }  ":="  {  return  BECOMES  ;  }  "="  {  returnera  EQL  ;  }  "<>"  {  return  NEQ  ;  }  "<"  {  returnera  LSS  ;  }  ">"  {  return  GTR  ;  }  "<="  {  return  LEQ  ;  }  ">="  {  return  GEQ  ;  }  "begin"  {  return  BEGINSYM  ;  }  "call"  {  return  CALLSYM  ;  }  "const"  {  return  CONSTSYM  ;  }  "gör"  {  return  DOSYM  ;  }  "slut"  {  return  ENDSYM  ;  }  "if"  {  return  IFSYM  ;  }  "udda"  {  return  ODDSYM  ;  }  "procedur"  {  return  PROCSYM  ;  }  "då"  {  return  THENSYM  ;  }  "var"  {  return  VARSYM  ;  }  "while"  {  return  WHILESYM  ;  }  {  bokstav  }({  bokstav  }  |  {  siffra  })  *  {  yylval  .  id  =  strdup  (  yytext  );  returnera  IDENT  ;  }  {  siffra  }  +  {  yylval  .  num  =  atoi  (  yytext  );  returnera  NUMBER  ;  }  [  \  t  \  n  \  r  ]  /* hoppa över blanksteg */  .  {  printf  (  "Okänt tecken [%c]  \n  "  ,  yytext  [  ]);  returnera  OKÄNT  ;  }  %%  int  yywrap  (  void  ){  return  1  ;}

Interner

Dessa program utför karaktärsanalys och tokenisering med hjälp av en deterministisk finit automat (DFA). En DFA är en teoretisk maskin som accepterar vanliga språk . Dessa maskiner är en delmängd av samlingen av Turing-maskiner . DFA:er är likvärdiga med skrivskyddade högerflyttande Turing-maskiner . Syntaxen är baserad på användningen av reguljära uttryck . Se även icke-deterministisk finit automat .

frågor

Tidskomplexitet

En Flex lexical analysator har vanligtvis tidskomplexitet $O(n)$ i längden på inmatningen. Det vill säga, den utför ett konstant antal operationer för varje ingångssymbol. Denna konstant är ganska låg: GCC genererar 12 instruktioner för DFA-matchningsslingan. ^{[ citat behövs ]} Observera att konstanten är oberoende av längden på token, längden på det reguljära uttrycket och storleken på DFA.

Men att använda REJECT-makrot i en skanner med potential att matcha extremt långa tokens kan göra att Flex genererar en skanner med icke-linjär prestanda. Denna funktion är valfri. I det här fallet har programmeraren uttryckligen sagt till Flex att "gå tillbaka och försöka igen" efter att den redan har matchat någon indata. Detta kommer att få DFA att backa för att hitta andra accepterande tillstånd. AVVISA-funktionen är inte aktiverad som standard, och på grund av dess prestandaimplikationer avråds användningen av den i Flex-manualen.

Återinträde

Som standard är skannern som genereras av Flex inte återkommande . Detta kan orsaka allvarliga problem för program som använder den genererade skannern från olika trådar. För att övervinna detta problem finns det alternativ som Flex tillhandahåller för att uppnå återinträde. En detaljerad beskrivning av dessa alternativ finns i Flex-manualen.

Användning i icke-Unix-miljöer

Normalt innehåller den genererade skannern referenser till unistd.h -huvudfilen, som är Unix- specifik. För att undvika att generera kod som inkluderar unistd.h , bör %option nounistd användas. Ett annat problem är anropet till isatty (en Unix-biblioteksfunktion), som finns i den genererade koden. Alternativet % never-interactive tvingar flex att generera kod som inte använder isatty .

Använder flex från andra språk

Flex kan bara generera kod för C och C++ . För att använda skannerkoden som genereras av flex från andra språk kan ett språkbindningsverktyg som SWIG användas.

Unicode-stöd

Flex är begränsat till matchande 1-byte (8-bitars) binära värden och stöder därför inte Unicode . RE/flex och andra alternativ stöder Unicode-matchning.

Flex++

flex++ är en liknande lexikalskanner för C++ som ingår som en del av flexpaketet. Den genererade koden är inte beroende av någon körtid eller externt bibliotek förutom en minnesallokator ( malloc eller ett alternativ som tillhandahålls av användaren) om inte ingången också beror på den. Detta kan vara användbart i inbäddade och liknande situationer där traditionella operativsystem eller C runtime faciliteter kanske inte är tillgängliga.

Den flex++-genererade C++-skannern inkluderar rubrikfilen FlexLexer.h , som definierar gränssnitten för de två C++-genererade klasserna.

Se även

Vidare läsning

Levine, John (augusti 2009). flex & bison . O'Reilly Media. ISBN 978-0-596-15597-1 .
ME Lesk och E. Schmidt, LEX - Lexical Analyzer Generator
Alfred Aho, Ravi Sethi och Jeffrey Ullman, Compilers: Principles, Techniques and Tools , Addison-Wesley (1986). Beskriver de mönstermatchningstekniker som används av flex (deterministiska finita automater)

externa länkar