Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>I'm not an expert at packrat parsing, but you can learn more at <a href="https://en.wikipedia.org/wiki/Parsing_expression_grammar" rel="nofollow">Parsing expression grammar on Wikipedia</a>.</p> <p>I haven't dug into it so I'll assume the linear-time characterization of packrat parsing is correct.</p> <p>L(AL)R parsers <em>are</em> linear time parsers too. So in theory, neither packrat nor L(AL)R parsers are "faster".</p> <p>What matters, in practice, of course, is implementation. L(AL)R state transitions can be executed in very few machine instructions ("look token code up in vector, get next state and action") so they can be extremely fast in practice. By "compiling" L(AL)R parsing to machine code, you can end up with lightning fast parsers, as shown by <a href="http://portal.acm.org/citation.cfm?id=13326&amp;dl=" rel="nofollow">this 1986 Tom Pennello paper on Very Fast LR parsing</a>. (Machines are now 20 years faster than when <em>he</em> wrote the paper!).</p> <p>If packrat parsers are storing/caching results as they go, they may be linear time, but I'd guess the constant overhead would be pretty high, and then L(AL)R parsers in practice would be much faster. The YACC and Bison implementations from what I hear are pretty good. </p> <p>If you care about the answer, read the basic technical papers closely; if you <em>really</em> care, then implement one of each and check out the overhead constants. My money is strongly on L(AL)R.</p> <p>An observation: most language front-ends don't spend most of their time "parsing"; rather, they spend a lot of time in lexical analysis. Optimize that (your bio says you are), and the parser speed won't matter much.</p> <p>(I used to build LALR parser generators and corresponding parsers. I don't do that anymore; instead I use <a href="https://en.wikipedia.org/wiki/GLR_parser" rel="nofollow">GLR parsers</a> which are linear time in practice but handle arbitrary context-free grammmars. I give up some performance, but I can [and do, see bio] build dozens of parsers for many languages without a lot of trouble.).</p>
    singulars
    1. This table or related slice is empty.
    1. POPackrat parsing vs. LALR parsing
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USRy-
    1. USIra Baxter
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POPackrat parsing vs. LALR parsing
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    3. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    1. COIt is possible to read the document (1986 Tom Pennello paper on Very Fast LR parsing) for free?
      singulars
      1. PO
      1. USraisyn
    2. COSure. Visit your local university's computer science library :-} I think the ACM will charge you only modest cost; IMHO its well worth it to make sure that ACM continues to make stuff like this available.
      singulars
      1. PO
      1. USIra Baxter
    3. CO@IraBaxter, are L(AL)R parsers scannerless the way packrat parsers are?
      singulars
      1. PO
      1. USMike Samuel
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload