parsing - How do you write a lexer parser where identifiers may begin with keywords? -


suppose have language identifiers might begin keywords. example, suppose "case" keyword, "caser" valid identifier. suppose lexer rules can handle regular expressions. seems can't place keyword rules ahead of identifier rule in lexer, because parse "caser" "case" followed "r". can't place keyword lexing rules after identifier rule, since identifier rule match keywords, , keyword rules never trigger.

so, instead, make keyword_or_identifier rule in lexer, , have parser determine if keyword_or_identifier keyword or identifier. done?

i realize "use different lexer has lookahead" answer (kind of), i'm interested in how done in traditional dfa-based lexer, since current lexer seems work way.

most lexers, starting original lex, match alternatives follows:

  1. use longest match.

  2. if there 2 or more alternatives tie longest match, use first 1 in lexer definition.

this allows following style:

"case"                  { return case; } [[:alpha:]][[:alnum:]]* { return id; }

if input pattern caser, second alternative used because it's longest match. if input pattern case r, first alternative used because both of them match case, , rule (2) above, first 1 wins.

although may seem bit arbitrary, it's consistent dfa approach, mostly. first of all, dfa doesn't stop first time reaches accepting state. if did, patterns [[:alpha:]][[:alnum:]]* useless, because enter accepting state on first character (assuming alphabetic). instead, dfa-based lexers continue until there no possible transitions current state, , until last accepting state. (see below.)

a given dfa state may accepting because of 2 different rules, that's not problem either; first accepting rule recorded.

to fair, different mathematical model of dfa, has transition every symbol in every state (although many of them may transitions "sink" state), , matches complete input depending on whether or not automaton in accepting state when last symbol of input read. lexer model different, can formalized well.

the difficulty in theoretical model "back last accepting state". in practice, done remembering state , input position every time accepting state reached. mean may necessary rewind input stream, possibly arbitrary amount.

most languages not require backup often, , few require indefinite backup. lexer generators can generate faster code if there no backup states. (flex if use -cf or -cf.)

one common case leads indefinite backup failing provide appropriate error return string literals:

["][^"\n]*["]    { return string; }  /* ... */ .                { return invalid; }

here, first pattern match string literal starting " if there matching " on same line. (i omitted \-escapes simplicity.) if string literal unterminated, last pattern match, input need rewound ". in cases, it's pointless trying continue lexical analysis ignoring unmatched "; make more sense ignore entire remainder of line. not backing inefficient, lead explosion of false error messages. better solution might be:

["][^"\n]*["]    { return string; }  ["][^"\n]*       { return invalid_string; }

here, second alternative can succeed if string unterminated, because if string terminated, first alternative match 1 more character. consequently, doesn't matter in order these alternatives appear, although know put them in same order did.


Comments

Post a Comment

Popular posts from this blog

php - Why I am getting the Error "Commands out of sync; you can't run this command now" -

the documentation of error mentioned in title says if commands out of sync; can't run command now in client code, calling client functions in wrong order. this can happen, example, if using mysql_use_result() , try execute new query before have called mysql_free_result(). can happen if try execute 2 queries return data without calling mysql_use_result() or mysql_store_result() in between. from here: http://dev.mysql.com/doc/refman/5.0/en/commands-out-of-sync.html but in first query not fetching data mysql database, inserting. , in second query getting data database. here code $connection = mysqli_connect("localhost","username","password","tbl_msgs"); if(mysqli_connect_errno($connection)) { die("failed connect mysql: " . mysqli_connect_error()); } $query = "insert users (total_comments, total_views) values ({$total_comments}, {$total_views});"; $query .= "insert msgs (no...
Read more

linux - Does gcc have any options to add version info in ELF binary file? -

i mean whether gcc can insert source code version infor elf binary section or similar. not want change source file, add info gcc option in makefile. you can emit version info text file, turn text file object file statically link executable. the first step simple have write code: script or write version info in format plain text file. write makefile rule produce version.o version.txt, using objcopy . you'll have object file 2 useful symbols defined in it: beginning , end of textual version info. add generated object executable, , you'll able access version 2 ways: running strings on binary, or writing code in application print version string (you'll need declare start , end symbols variables in header file).
Read more

java - Are there any classes that implement javax.persistence.Parameter<T>? -

i'm using named queries fetch entities database using jpa , hibernate , came across puzzling me: how come there no default implementations of javax.persistence.parameter interface? i rather impressed how @staticmetamodel used criteriabuilder in jpa2 meaning type safety , don't have mess around setting string names. wanted apply similar of jpa1 ejb's i'm working on: dealergroup_.class: public dealergroup_ { public parameter<integer> id = new parameterimpl<integer>("id"); /// etc... } dealergroupfacade.class: // ... public dealergroup fetch(integer id) { typedquery<dealergroup> query = em.createnamedquery("dealergroup.fetchbyid", dealergroup.class); query.setparameter(dealergroup_.id, query); return query.getsingleresult(); } // ... i surprised find there no implementations of parameter interface - of course, implement myself absence makes me suspicious may mistake using in way? should implementing parameter...
Read more