parsing - Performance of parsers: PEG vs LALR(1) or LL(k) -


i've seen claims optimized peg parsers in general cannot faster optimized lalr(1) or ll(k) parsers. (of course, performance of parsing depend on particular grammar.)

i'd know if there specific limitations of peg parsers, either valid in general or subsets of peg grammars make them inferior lalr(1) or ll(k) performance-wise.

in particular, i'm interested in parser generators, assume output can tweaked performance in particular case. assume parsers optimized , possible tweak particular grammar bit if that's needed improve performance.

found answer packrat vs lalr parsing. quotes it:

l(al)r parsers linear time parsers, too. in theory, neither packrat nor l(al)r parsers "faster".

what matters, in practice, of course, implementation. l(al)r state transitions can executed in few machine instructions ("look token code in vector, next state , action") can extremely fast in practice.

an observation: language front-ends don't spend of time "parsing"; rather, spend lot of time in lexical analysis. optimize ..., , parser speed won't matter much.


Comments

Post a Comment

Popular posts from this blog

javascript - backbone.js Collection.add() doesn't `construct` (`initialize`) an object -

<!doctype html public "-//w3c//dtd xhtml 1.0 strict//en" "http://www.w3.org/tr/xhtml1/dtd/xhtml1-strict.dtd"> <html> <head> <script src="https://ajax.googleapis.com/ajax/libs/jquery/1.7.2/jquery.min.js"></script> <script src="http://documentcloud.github.com/underscore/underscore-min.js"></script> <script src="http://documentcloud.github.com/backbone/backbone-min.js"></script> </head> <body> <button id="cmd_create_event" name="cmd_create_event" type="button">create new `event`</button> <script type="text/javascript"> var eventmodel = backbone.model.extend({ initialize : function() { console.log("`event` initialized. id: " + this.cid); this.bind("change:status", function() { console.log(this.get("status") + " value `status`"); }); this.bind("error", function(model, e...
Read more

php - Get uncommon values from two or more arrays -

is there function in php give array of uncommon values 2 or more arrays? for example: $array1 = array( "green", "red", "blue"); $array2 = array( "green", "yellow", "red"); .... $result = function_needed($array1, $array2,...); print_r($result); should give output: array("blue", "yellow", ...); use array_diff , array_merge : $result = array_merge(array_diff($array1, $array2), array_diff($array2, $array1)); here's demo. for multiple arrays, combine callback , array_reduce : function unique(&$a, $b) { return $a ? array_merge(array_diff($a, $b), array_diff($b, $a)) : $b; } $arrays = array( array('green', 'red', 'blue'), array('green', 'yellow', 'red') ); $result = array_reduce($arrays, 'unique'); and here's demo of that.
Read more

Adding duplicate array rows in Php -

i create function in php adds rows of array shared column value. so input. $test = array( array("c", 5, 6), array("c", 2, 3), array("test", 5, 6) ); and output. $testduplicatefree = array( array("c", 7, 9), array("test", 5, 6) ) ); i'm thinking function combine_duplicates($array,$col){ ... ... return $duplicatefreearray; } where $col duplicate free array. so, in case, combine_duplicates($test,0); would me desired output. this. <?php function combine_duplicates($array,$col) { $index = array(); foreach ($array $row) { $key = $row[$col]; if (!isset($index[$key])) { $index[$key] = $row; } else { ($i = 0; $i < count($row); ++$i) { if ($i != $col) { $index[$key][$i] += $row[$i]; } } } } return array_values($index); } $array = array( array("c", 5, 6), array("c", 2, 3), array("test", 5, 6) ); print_r(combine_duplicates($array, 0)); try here: http://codepad.org/mdhesqhi
Read more