752:(CFG), dividing the ID/LP Grammar into an Ordered Context Free Grammar (CFG) and Unordered Context Free Grammar (UCFG). This allows the two algorithms to parse strings more efficiently; in particular, the Earley Parser uses a point tracking method that follows a linear path established by the LP rules. In a CFG, LP rules do not allow repeated constituents in the parsed string, but an UCFG allows repeated constituents within the parsed strings. If the ID/LP Grammar is converted to a UCFG then the LP rules do not dominate during the parsing process, however, it still follows the point tracking method.
310:
1060:) is accepted within the main string. It does this by looking whether the produced individual strings are found in the Parse List. If one or all of the individual strings are not found within the Parse List, then the overall string will fail. If one or all of the individual strings are found in the Parse List, then the overall string will be accepted.
1292:, Y!, and generates each string individually instead of using one string to represent the repeated parsed strings. Whenever the dot moves over one element, the algorithm begins to generate parsed strings of the elements on the right edge in random positions until there are no more elements in the right edge set. Let
5046:
Notice how the
Unordered version of ID/LP Grammar contains mush less strings than the UCFG; Shieber's Algorithm use one string to represent the multiple different strings for repeated elements. Both algorithms can parse Ordered Grammars equally, however, Shieber's Algorithm seems to be more efficient
1068:
The UCFG is the appropriate equivalent to convert the ID/LP Grammar into in order to use the Earley Parser. This algorithm read strings similarly to how it parses CFG, however, in this case the order of elements is not enforced; resulting in lack of LP rule enforcement. This allows some elements to
150:
and its daughters, where the mother node (to the left of the arrow) is said to immediately dominate the daughter nodes (those to the right of the arrow), but the daughters do not immediately dominate the mother. The daughter nodes are also dominated by any node that immediately dominates the mother
443:
that follows at least one ID rule and all LP statements of the grammar. If every possible string generated by the grammar fits this criterion, than it is an ID/LP Grammar. Additionally, for a grammar to be able to be written in ID/LP format, it must have the property of
Exhaustive Constant Partial
426:
as well. LP relationships are asymmetric: if B precedes C, C can never precede B. An LP relationship where there can be no intervening nodes is called immediate precedence, while an LP where there can be intervening nodes (those derived from the principle of transitivity) are said to have weak
607:
4511:
The
Unordered ID/LP Grammar follow the above, 6 step algorithm, in order to parse the strings. The noticeable difference is in the productions of each set list; there is one string that represents the many individual strings within one list. The table below shows the set list of
3261:
Steps 2-3 are repeated exhaustively until no more new items can be added and then continue on to Step 4. Steps 5-6 are also exhaustively repeated until no further new items can be added to the set list. The string will be accepted if a string behaves or resembles the production,
1812:
The Earley Parser applies each string to the individual rules of a grammar and this results in very large sets.The large sets is partly resulted in the conversion of ID/LP Grammar into an equivalent grammar, however, parsing the overall ID/LP Grammar is difficult to begin with.
592:
212:
Linear precedence is the order relationship of sister nodes. LP constraints specify in what order sister nodes under the same mother can appear. Nodes that surface earlier in strings precede their sisters. LP can be shown in phrase structure rules in the form
1834:
Parsing an ID/LP Grammar, directly, generates a set list that will determine whether the production of the string will be accepted or fail. The algorithm follows 6 Steps (the symbols used can also represents the
Syntactic Categories):
723:.This property of ID/LP Grammars enables easier cross linguistic generalizations by describing the language specific differences in constituent order with LP statements, separately from the ID rules that are similar across languages.
1821:
The foundation of
Shieber's Algorithm is based on the Earley Parser for CFG, however, it does not require the ID/LP Grammar to be converted into a different grammar in order to be parsed. ID rules can be parsed in a separate form, S
256:
70:, indicating that an S-node dominates an NP-node and a VP-node, and that the NP precedes the VP in the surface string. In ID/LP Grammars, this rule would only indicate dominance, and a linear precedence statement, such as
1284:
1136:
1190:
653:
Separating LP requirements from ID rules also accounts for the phenomena of free word order in natural language. For example, in
English it is possible to put adverbs before or after a verb and have both strings be
128:
also attempts to distinguish between dominance and ordering. For instance, recent papers by Noam
Chomsky have proposed that, while hierarchical structure is the result of the syntactic structure-building operation
974:
910:
871:
1058:
743:
ID and LP rules impose constraints on sentence strings; when dealing with large strings, the constraints of these rules can cause the parsed string to become infinite, thus making parsing difficult. The
3392:
196:, shows that the node labelled A (mother node) immediately dominates nodes labelled B, C, and D, (daughter nodes) and nodes labelled B, C, and D can be immediately dominated by a node labelled A.
5043:
results in a similar string as the ordered ID/LP Grammar; however, the order of the items within the string is not enforced. The final string is accepted as it matches the original string's elements.
2428:
1022:
3533:
3486:
3439:
1079:
The production of the completed string. In this case, the position of the two sets in the origin position will swap; the filled set is on the left edge and the empty set is on the right edge.
1826:{V, NP, S}, from the LP rules, V < S. Shieber compared parsing of a CFG to an ordered ID/LP Grammar string and Barton compared the parsing of a UCFG to an unordered ID/LP Grammar string.
68:
200:
303:
816:
721:
530:
486:
249:
194:
2595:
4371:
1480:
1394:
1224:
4908:
4813:
4718:
4623:
4235:
4049:
3808:
3607:
3333:
3255:
3182:
3130:
3042:
2966:
2914:
2832:
2756:
2680:
2504:
2390:
2338:
2248:
2170:
2078:
1945:
1913:
3156:
2940:
2654:
2364:
2124:
606:
31:
incorporate dominance and precedence into a single rule, ID/LP Grammars maintains separate rule sets which need not be processed simultaneously. ID/LP Grammars are used in
780:
580:, where V is the head of a VP, this means that in any clause in any sentence, V will always surface before its DP sister in any context, as seen in the following examples.
203:
The node labelled A immediately dominates the nodes B, C, and D, and the node labelled B immediately dominates C' and D'. A also dominates C' and D', but not immediately
100:
640:
578:
133:, linear order is not determined by this operation, and is simply the result of externalization (oral pronunciation, or, in the case of sign language, manual signing).
3562:
424:
398:
372:
339:
2628:
2144:
2098:
932:
551:
Since LP statements apply regardless of the ID rule context, they allow us to make generalizations across the whole grammar. For example, given the LP statement
5041:
4577:
4501:
4423:
4283:
4153:
4097:
3967:
3915:
3856:
3726:
3673:
4971:
4876:
4781:
4686:
4333:
4202:
4016:
3775:
3304:
3226:
3101:
3013:
2885:
2803:
2727:
2560:
2472:
2309:
2219:
2049:
1991:
1884:
1808:
1756:
1702:
1650:
1596:
1544:
591:
5091:
Gazdar, Gerald; Pullum, Geoffrey K. (1981). "Subcategorization, constituent order, and the notion 'head'". In M. Moortgat; H.v.d. Hulst; T. Hoekstra (eds.).
650:. Non-ID/LP Grammars are unable to make such generalizations across the whole grammar, and so must repeat ordering restrictions for each individual context.
118:
1234:
1086:
1143:
444:
Ordering (ECPO): namely that at least part of the ID/LP relations in one rule is observed in all other rules. For example, the set of rules:
942:
878:
839:
1069:
be repeated within the parsed strings and the UCFG accepts empty multi-sets along with filled multi-sets within its strings. For example:
305:. Since there is no fixed order for the daughter nodes, it is possible that all three of the trees shown here are generated by this rule.
1029:
5155:
3341:
2395:
1076:
The current position of the dot which predicts the following set; the element that the dot passed will move into the empty set.
983:
3494:
3447:
3400:
5056:
760:
After the ID/LP Grammar has been converted to the equivalent form within a CFG, the algorithm will analyze the string. Let
110:
106:
5340:
309:
5323:
5138:
5469:
255:
27:
by distinguishing between immediate dominance (ID) and linear precedence (LP) constraints. Whereas traditional
5100:
41:
264:
789:
682:
497:
453:
216:
161:
5464:
261:
A rule that has ID constraints but not LP is written with commas between the daughter nodes, for example
2565:
4344:
1400:
1311:
1197:
114:
4884:
4789:
4694:
4599:
4211:
4025:
3784:
3583:
3309:
3231:
3161:
3106:
3018:
2945:
2890:
2808:
2732:
2659:
2480:
2369:
2314:
2224:
2149:
2054:
1921:
1889:
5436:
5061:
1288:
When parsing a string that contains a number of unordered elements, the Earley Parser treats it as a
436:
32:
3135:
2919:
2633:
2343:
2103:
647:
20:
763:
315:
Alternatively, these relationships can be expressed through linear precedence statements, such as
73:
5227:
Chomsky, Noam (2011). "Language and other cognitive systems. What is special about language?".
676:
616:
554:
28:
3541:
403:
377:
351:
318:
2600:
826:
The original position of the dot; it usually begins with the left-most element of the string.
440:
5163:
Proceedings of the
Eleventh International Conference on Head-Driven Phrase Structure Grammar
2129:
2083:
917:
749:
155:
8:
345:
130:
5244:
5209:
5174:
4981:
4517:
4428:
4375:
4241:
4102:
4055:
3919:
3861:
3814:
3678:
3613:
819:
643:
125:
4914:
4819:
4724:
4629:
4288:
4157:
3971:
3730:
3265:
3187:
3050:
2971:
2837:
2764:
2685:
2509:
2433:
2256:
2175:
1996:
1950:
1843:
1761:
1709:
1655:
1603:
1549:
1497:
5319:
5285:
5280:
5263:
5248:
5213:
5134:
5127:
5096:
679:
would require two separate rules, but this can be described by the single ID/LP rule
5341:
Generalized ID/LP grammar: a formalism for parsing linearization-based HPSG grammars
5192:
Chomsky, Noam (2007). "Biolinguistic explorations: Design, development, evolution".
5178:
5275:
5236:
5201:
5166:
146:
Immediate dominance is the asymmetrical relationship between the mother node of a
5240:
5124:
1279:{\displaystyle \mathrm {X} \longrightarrow \{\alpha ,\beta ,\iota \}\cdot \{\}}
1131:{\displaystyle \mathrm {X} \longrightarrow \{\}\cdot \{\alpha ,\beta ,\iota \}}
1073:
The origin position of the dot; it is between the empty set and the filled set.
24:
5205:
1185:{\displaystyle \mathrm {X} \longrightarrow \{\alpha \}\cdot \{\beta ,\iota \}}
5458:
5071:
1026:
which the list will help determine whether the completed production element (
745:
732:
5390:
978:
The parsed strings are then used together to form a Parse List for example:
5289:
5170:
1289:
5125:
Gazdar, Gerald; Ewan H. Klein; Geoffrey K. Pullum; Ivan A. Sag (1985).
822:. The algorithm then analyzes the string and identifies the following:
147:
1491:
will produce, 3! = 6, different parsed strings of the right edge set:
969:{\displaystyle \mathrm {X} \longrightarrow \alpha \beta \iota \cdot }
905:{\displaystyle \mathrm {X} \longrightarrow \alpha \cdot \beta \iota }
866:{\displaystyle \mathrm {X} \longrightarrow \cdot \alpha \beta \iota }
829:
The current position of the dot; this predicts the following element.
5401:(4): 205–218 – via Association for Computational Linguistics.
199:
5133:. Oxford: Blackwell, and Cambridge, MA: Harvard University Press.
5090:
5066:
4506:
1053:{\displaystyle \mathrm {X} \longrightarrow \alpha \beta \iota }
613:
This can be generalized into a rule that holds across
English,
748:
solves this by altering the format of an ID/LP Grammar into a
341:, to mean that anytime B and C are sisters, B must precede C.
1829:
731:
Two parsing algorithms used to parse ID/LP Grammars are the
251:
to mean B precedes C precedes D, as shown in the tree below.
5346:
5153:
818:
stand for the elements of the string and it also represents
439:
to be grammatical in an ID/LP Grammar, it must belong to a
151:
node, however this is not an immediate dominance relation.
4425:
is accepted and produces the following production string:
3387:{\displaystyle S\longrightarrow _{\mathrm {ID} }\{C,D,F\}}
2423:{\displaystyle Z\longrightarrow _{\mathrm {ID} }\lambda }
1017:{\displaystyle \mathrm {I} _{0}\ldots \mathrm {I} _{n}}
5156:"GIDLP: A grammar format for linearization-based HPSG"
3528:{\displaystyle F\longrightarrow _{\mathrm {ID} }\{f\}}
3481:{\displaystyle D\longrightarrow _{\mathrm {ID} }\{d\}}
3434:{\displaystyle C\longrightarrow _{\mathrm {ID} }\{c\}}
4984:
4917:
4887:
4822:
4792:
4727:
4697:
4632:
4602:
4520:
4431:
4378:
4347:
4291:
4244:
4214:
4160:
4105:
4058:
4028:
3974:
3922:
3864:
3817:
3787:
3733:
3681:
3616:
3586:
3544:
3497:
3450:
3403:
3344:
3312:
3268:
3234:
3190:
3164:
3138:
3109:
3053:
3021:
2974:
2948:
2922:
2893:
2840:
2811:
2767:
2735:
2688:
2662:
2636:
2603:
2568:
2512:
2483:
2436:
2398:
2372:
2346:
2317:
2259:
2227:
2178:
2152:
2132:
2106:
2086:
2057:
1999:
1953:
1924:
1892:
1846:
1764:
1712:
1658:
1606:
1552:
1500:
1403:
1314:
1237:
1200:
1146:
1089:
1032:
986:
945:
920:
881:
842:
792:
766:
685:
619:
557:
500:
456:
406:
380:
354:
321:
267:
219:
164:
76:
44:
38:
For example, a typical phrase structure rule such as
5345:(Electronic Thesis or Dissertation). Retrieved from
136:
430:
348:can be applied to LP relations which means that if
5261:
5126:
5035:
4965:
4902:
4870:
4807:
4775:
4712:
4680:
4617:
4571:
4495:
4417:
4365:
4327:
4277:
4229:
4196:
4147:
4091:
4043:
4010:
3961:
3909:
3850:
3802:
3769:
3720:
3667:
3601:
3556:
3527:
3480:
3433:
3386:
3327:
3298:
3249:
3220:
3176:
3150:
3124:
3095:
3036:
3007:
2960:
2934:
2908:
2879:
2826:
2797:
2750:
2721:
2674:
2648:
2622:
2589:
2554:
2498:
2466:
2422:
2384:
2358:
2332:
2303:
2242:
2213:
2164:
2138:
2118:
2092:
2072:
2043:
1985:
1939:
1907:
1878:
1802:
1750:
1696:
1644:
1590:
1538:
1474:
1388:
1278:
1218:
1184:
1130:
1052:
1016:
968:
926:
904:
865:
810:
774:
738:
715:
634:
572:
524:
480:
418:
392:
366:
333:
297:
243:
188:
94:
62:
5456:
5316:A Course in Generalized Phrase Structure Grammar
546:
5194:International Journal of Philosophical Studies
2430:then the next item can be added to this list,
5226:
5191:
109:; the ID/LP Grammar approach is also used in
105:The idea first came to prominence as part of
4554:
4536:
4507:Direct Parsing of an Unordered ID/LP Grammar
4182:
4176:
4130:
4124:
3996:
3990:
3944:
3938:
3892:
3880:
3755:
3749:
3703:
3697:
3650:
3632:
3522:
3516:
3475:
3469:
3428:
3422:
3381:
3363:
3075:
3069:
2859:
2853:
2534:
2528:
2283:
2277:
2023:
2017:
1460:
1442:
1436:
1430:
1374:
1350:
1344:
1341:
1273:
1270:
1264:
1246:
1213:
1201:
1179:
1167:
1161:
1155:
1125:
1107:
1101:
1098:
726:
5388:
1830:Direct Parsing of an Ordered ID/LP Grammar
55:
5279:
1306:as the first parsed string; for example:
1063:
539:says that C must always precede D, while
535:does not have the ECPO property, because
5447:(2): 1–30 – via SRI International.
5262:Berwick, Robert C.; et al. (2011).
755:
198:
63:{\displaystyle {\ce {S -> NP \; VP}}}
5434:
5313:
5154:Daniels, Mike; Meurers, Detmar (2004).
1886:to the initial item in the parse list,
832:The production of the completed string.
5457:
5430:
5428:
1816:
298:{\displaystyle A\rightarrow B,\ C,\ D}
141:
5426:
5424:
5422:
5420:
5418:
5416:
5414:
5412:
5410:
5408:
5384:
5382:
5380:
5378:
5376:
5374:
811:{\displaystyle \alpha ,\beta ,\iota }
5391:"On the Complexity of ID/LP Parsing"
5372:
5370:
5368:
5366:
5364:
5362:
5360:
5358:
5356:
5354:
5309:
5307:
5305:
5303:
5301:
5299:
5129:Generalized Phrase Structure Grammar
5120:
5118:
5116:
5114:
5112:
5057:Generalized Phrase Structure Grammar
716:{\displaystyle VP\rightarrow V,AdvP}
525:{\displaystyle B\rightarrow D\ C\ A}
481:{\displaystyle A\rightarrow B\ C\ D}
244:{\displaystyle A\rightarrow B\ C\ D}
207:
189:{\displaystyle A\rightarrow B\ C\ D}
111:head-driven phrase structure grammar
107:Generalized Phrase Structure Grammar
5264:"Poverty of the stimulus revisited"
5047:when parsing an Unordered Grammar.
2477:This step will build the set list,
2080:does not allow Z to be preceded by
543:says that D must always precede C.
13:
5437:"Direct Parsing of ID/LP Grammars"
5405:
5018:
4951:
4890:
4856:
4795:
4761:
4700:
4666:
4605:
4400:
4350:
4313:
4260:
4217:
4074:
4031:
3833:
3790:
3589:
3510:
3507:
3463:
3460:
3416:
3413:
3357:
3354:
3315:
3237:
3112:
3024:
2896:
2814:
2738:
2682:then the following item is added,
2590:{\displaystyle \mathrm {I} _{n-1}}
2571:
2486:
2411:
2408:
2320:
2264:
2230:
2183:
2060:
2004:
1958:
1927:
1895:
1857:
1769:
1717:
1663:
1611:
1557:
1505:
1423:
1406:
1334:
1317:
1299:represent the original string and
1239:
1148:
1091:
1034:
1004:
989:
947:
883:
844:
768:
14:
5481:
5351:
5296:
5229:Language Learning and Development
5109:
4366:{\displaystyle \mathrm {I} _{3},}
1475:{\displaystyle \mathrm {X} _{1}:}
1389:{\displaystyle \mathrm {X} _{0}:}
1219:{\displaystyle \{\beta ,\iota \}}
137:Defining Dominance and Precedence
5281:10.1111/j.1551-6709.2011.01189.x
4978:The complete production string,
4903:{\displaystyle \mathrm {I} _{3}}
4808:{\displaystyle \mathrm {I} _{2}}
4713:{\displaystyle \mathrm {I} _{1}}
4618:{\displaystyle \mathrm {I} _{0}}
4230:{\displaystyle \mathrm {I} _{3}}
4044:{\displaystyle \mathrm {I} _{2}}
3803:{\displaystyle \mathrm {I} _{1}}
3602:{\displaystyle \mathrm {I} _{0}}
3328:{\displaystyle \mathrm {I} _{n}}
3250:{\displaystyle \mathrm {I} _{n}}
3177:{\displaystyle Z\not \in \beta }
3125:{\displaystyle \mathrm {I} _{n}}
3037:{\displaystyle \mathrm {I} _{n}}
2961:{\displaystyle Z\not \in \beta }
2909:{\displaystyle \mathrm {I} _{i}}
2827:{\displaystyle \mathrm {I} _{n}}
2751:{\displaystyle \mathrm {I} _{n}}
2675:{\displaystyle q\not \in \beta }
2499:{\displaystyle \mathrm {I} _{n}}
2385:{\displaystyle Z\not \in \beta }
2333:{\displaystyle \mathrm {I} _{0}}
2243:{\displaystyle \mathrm {I} _{0}}
2165:{\displaystyle Z\not \in \beta }
2073:{\displaystyle \mathrm {I} _{0}}
1940:{\displaystyle \mathrm {I} _{0}}
1908:{\displaystyle \mathrm {I} _{0}}
605:
590:
431:Grammaticality in ID/LP Grammars
308:
254:
5389:Barton, Jr., G. Edward (1985).
739:Earley Parser in ID/LP Grammars
5332:
5255:
5220:
5185:
5147:
5084:
5027:
4985:
4960:
4918:
4865:
4823:
4770:
4728:
4675:
4633:
4563:
4521:
4490:
4487:
4475:
4471:
4459:
4455:
4443:
4433:
4409:
4379:
4322:
4292:
4269:
4245:
4191:
4161:
4139:
4106:
4083:
4059:
4005:
3975:
3953:
3923:
3901:
3865:
3842:
3818:
3764:
3734:
3712:
3682:
3659:
3617:
3502:
3455:
3408:
3349:
3293:
3269:
3215:
3191:
3151:{\displaystyle Z\nprec \beta }
3090:
3054:
3002:
2975:
2935:{\displaystyle Z\nprec \beta }
2874:
2841:
2792:
2768:
2716:
2689:
2649:{\displaystyle q\nprec \beta }
2549:
2513:
2461:
2437:
2403:
2359:{\displaystyle Z\nprec \beta }
2298:
2260:
2208:
2179:
2119:{\displaystyle Z\nprec \beta }
2038:
2000:
1980:
1954:
1873:
1847:
1797:
1773:
1765:
1745:
1721:
1713:
1691:
1667:
1659:
1639:
1615:
1607:
1585:
1561:
1553:
1533:
1509:
1501:
1469:
1427:
1419:
1383:
1338:
1330:
1243:
1152:
1095:
1038:
951:
887:
848:
692:
504:
460:
271:
223:
168:
49:
1:
5077:
2126:, and Z is not an element of
1840:For all of the ID rules, add
599:Ava told Sara to read a book.
5241:10.1080/15475441.2011.584041
2172:; then the following string,
775:{\displaystyle \mathrm {X} }
646:of any phrase and YP is its
547:Advantages of ID/LP Grammars
23:, differentiated from other
7:
5435:Shieber, Stuart M. (1983).
5050:
4341:The complete production of
10:
5486:
5441:Linguistics and Philosophy
5093:The scope of lexical rules
1918:If all of the elements in
115:lexical functional grammar
95:{\displaystyle NP\prec VP}
5395:Computational Linguistics
5347:https://etd.ohiolink.edu/
5206:10.1080/09672550601143078
5062:Computational Linguistics
4580:in an unordered grammar:
735:and Shieber's algorithm.
727:Parsing in ID/LP Grammars
635:{\displaystyle X\prec YP}
573:{\displaystyle V\prec DP}
346:principle of transitivity
33:Computational Linguistics
21:Phrase Structure Grammars
3557:{\displaystyle C\prec D}
2562:, that is an element of
419:{\displaystyle B\prec D}
393:{\displaystyle C\prec D}
367:{\displaystyle B\prec C}
334:{\displaystyle B\prec C}
2623:{\displaystyle q=q_{n}}
102:, would also be given.
5470:Generative linguistics
5314:Bennett, Paul (1995).
5037:
4967:
4904:
4872:
4809:
4777:
4714:
4682:
4619:
4573:
4497:
4419:
4367:
4329:
4279:
4231:
4198:
4149:
4093:
4045:
4012:
3963:
3911:
3852:
3804:
3771:
3722:
3669:
3603:
3558:
3529:
3482:
3435:
3388:
3329:
3300:
3251:
3222:
3178:
3152:
3126:
3097:
3038:
3009:
2962:
2936:
2910:
2881:
2828:
2799:
2752:
2723:
2676:
2650:
2624:
2591:
2556:
2500:
2468:
2424:
2386:
2360:
2334:
2305:
2244:
2215:
2166:
2140:
2139:{\displaystyle \beta }
2120:
2094:
2093:{\displaystyle \beta }
2074:
2045:
1987:
1941:
1909:
1880:
1804:
1752:
1698:
1646:
1592:
1540:
1476:
1390:
1280:
1220:
1186:
1132:
1064:Earley Parsing in UCFG
1054:
1018:
970:
928:
927:{\displaystyle \beta }
906:
867:
812:
776:
717:
673:
636:
611:
602:
588:
574:
533:
526:
489:
482:
420:
394:
368:
335:
299:
245:
204:
190:
96:
64:
29:phrase structure rules
5318:. London: UCL Press.
5038:
4968:
4905:
4873:
4810:
4778:
4715:
4683:
4620:
4574:
4498:
4420:
4368:
4330:
4280:
4232:
4199:
4150:
4094:
4046:
4013:
3964:
3912:
3853:
3805:
3772:
3723:
3670:
3604:
3559:
3530:
3483:
3436:
3389:
3330:
3301:
3252:
3223:
3179:
3153:
3127:
3098:
3039:
3010:
2963:
2937:
2911:
2882:
2829:
2800:
2753:
2724:
2677:
2651:
2625:
2592:
2557:
2501:
2469:
2425:
2387:
2361:
2335:
2306:
2245:
2216:
2167:
2141:
2121:
2095:
2075:
2046:
1988:
1942:
1910:
1881:
1805:
1753:
1699:
1647:
1593:
1541:
1477:
1391:
1281:
1221:
1187:
1133:
1055:
1019:
971:
929:
907:
868:
813:
777:
756:Earley Parsing in CFG
718:
656:
637:
603:
596:
582:
575:
527:
490:
483:
446:
421:
395:
369:
336:
300:
246:
202:
191:
97:
65:
5338:Daniels, M. (2005).
5171:10.21248/hpsg.2004.5
5095:. pp. 107–124.
4982:
4915:
4885:
4820:
4790:
4725:
4695:
4630:
4600:
4518:
4429:
4376:
4345:
4289:
4242:
4212:
4158:
4103:
4056:
4026:
3972:
3920:
3862:
3815:
3785:
3731:
3679:
3614:
3584:
3542:
3495:
3448:
3401:
3342:
3310:
3266:
3232:
3188:
3162:
3136:
3107:
3051:
3019:
2972:
2946:
2920:
2891:
2838:
2809:
2765:
2733:
2686:
2660:
2634:
2601:
2566:
2510:
2506:, more. Every item,
2481:
2434:
2396:
2370:
2344:
2315:
2257:
2225:
2176:
2150:
2130:
2104:
2084:
2055:
1997:
1993:, and the elements,
1951:
1922:
1890:
1844:
1762:
1710:
1656:
1604:
1550:
1498:
1401:
1312:
1235:
1227:are being predicted)
1198:
1144:
1087:
1030:
984:
943:
918:
879:
840:
820:Syntactic Categories
790:
764:
750:Context Free Grammar
683:
617:
555:
498:
454:
404:
378:
352:
319:
265:
217:
162:
124:Current work in the
119:unification grammars
74:
42:
4585:
3569:
3103:, is an element of
2805:, are elements of
1817:Shieber's Algorithm
935:is being predicted)
142:Immediate Dominance
5465:Grammar frameworks
5033:
4963:
4900:
4868:
4805:
4773:
4710:
4678:
4615:
4583:
4569:
4493:
4415:
4363:
4325:
4275:
4227:
4194:
4145:
4089:
4041:
4008:
3959:
3907:
3848:
3800:
3767:
3718:
3665:
3599:
3567:
3554:
3525:
3478:
3431:
3384:
3325:
3296:
3247:
3218:
3174:
3148:
3122:
3093:
3034:
3005:
2958:
2932:
2906:
2887:, are elements of
2877:
2824:
2795:
2748:
2719:
2672:
2646:
2620:
2587:
2552:
2496:
2464:
2420:
2382:
2356:
2330:
2311:, are elements of
2301:
2240:
2211:
2162:
2136:
2116:
2090:
2070:
2041:
1983:
1937:
1905:
1876:
1800:
1748:
1694:
1642:
1588:
1536:
1472:
1386:
1276:
1216:
1182:
1128:
1050:
1014:
966:
924:
902:
863:
808:
772:
713:
632:
585:Lucy won the race.
570:
522:
478:
416:
390:
364:
331:
295:
241:
205:
186:
126:Minimalist Program
92:
60:
5268:Cognitive Science
5036:{\displaystyle ,}
4976:
4975:
4572:{\displaystyle ,}
4496:{\displaystyle ]}
4418:{\displaystyle ,}
4339:
4338:
4278:{\displaystyle ,}
4148:{\displaystyle ,}
4092:{\displaystyle ,}
3962:{\displaystyle ,}
3910:{\displaystyle ,}
3851:{\displaystyle ,}
3721:{\displaystyle ,}
3668:{\displaystyle ,}
3306:is an element of
642:, where X is the
518:
512:
474:
468:
291:
282:
237:
231:
208:Linear Precedence
182:
176:
154:For example, the
58:
54:
48:
5477:
5449:
5448:
5432:
5403:
5402:
5386:
5349:
5336:
5330:
5329:
5311:
5294:
5293:
5283:
5274:(7): 1207–1242.
5259:
5253:
5252:
5224:
5218:
5217:
5189:
5183:
5182:
5160:
5151:
5145:
5144:
5132:
5122:
5107:
5106:
5088:
5042:
5040:
5039:
5034:
4972:
4970:
4969:
4966:{\displaystyle }
4964:
4909:
4907:
4906:
4901:
4899:
4898:
4893:
4877:
4875:
4874:
4871:{\displaystyle }
4869:
4814:
4812:
4811:
4806:
4804:
4803:
4798:
4782:
4780:
4779:
4776:{\displaystyle }
4774:
4719:
4717:
4716:
4711:
4709:
4708:
4703:
4687:
4685:
4684:
4681:{\displaystyle }
4679:
4624:
4622:
4621:
4616:
4614:
4613:
4608:
4586:
4582:
4578:
4576:
4575:
4570:
4502:
4500:
4499:
4494:
4483:
4482:
4467:
4466:
4451:
4450:
4441:
4440:
4424:
4422:
4421:
4416:
4372:
4370:
4369:
4364:
4359:
4358:
4353:
4334:
4332:
4331:
4328:{\displaystyle }
4326:
4284:
4282:
4281:
4276:
4236:
4234:
4233:
4228:
4226:
4225:
4220:
4203:
4201:
4200:
4197:{\displaystyle }
4195:
4154:
4152:
4151:
4146:
4098:
4096:
4095:
4090:
4050:
4048:
4047:
4042:
4040:
4039:
4034:
4017:
4015:
4014:
4011:{\displaystyle }
4009:
3968:
3966:
3965:
3960:
3916:
3914:
3913:
3908:
3857:
3855:
3854:
3849:
3809:
3807:
3806:
3801:
3799:
3798:
3793:
3776:
3774:
3773:
3770:{\displaystyle }
3768:
3727:
3725:
3724:
3719:
3674:
3672:
3671:
3666:
3608:
3606:
3605:
3600:
3598:
3597:
3592:
3570:
3566:
3563:
3561:
3560:
3555:
3534:
3532:
3531:
3526:
3515:
3514:
3513:
3487:
3485:
3484:
3479:
3468:
3467:
3466:
3440:
3438:
3437:
3432:
3421:
3420:
3419:
3393:
3391:
3390:
3385:
3362:
3361:
3360:
3334:
3332:
3331:
3326:
3324:
3323:
3318:
3305:
3303:
3302:
3299:{\displaystyle }
3297:
3256:
3254:
3253:
3248:
3246:
3245:
3240:
3227:
3225:
3224:
3221:{\displaystyle }
3219:
3183:
3181:
3180:
3175:
3157:
3155:
3154:
3149:
3131:
3129:
3128:
3123:
3121:
3120:
3115:
3102:
3100:
3099:
3096:{\displaystyle }
3094:
3043:
3041:
3040:
3035:
3033:
3032:
3027:
3014:
3012:
3011:
3008:{\displaystyle }
3006:
2967:
2965:
2964:
2959:
2941:
2939:
2938:
2933:
2915:
2913:
2912:
2907:
2905:
2904:
2899:
2886:
2884:
2883:
2880:{\displaystyle }
2878:
2833:
2831:
2830:
2825:
2823:
2822:
2817:
2804:
2802:
2801:
2798:{\displaystyle }
2796:
2757:
2755:
2754:
2749:
2747:
2746:
2741:
2728:
2726:
2725:
2722:{\displaystyle }
2720:
2681:
2679:
2678:
2673:
2655:
2653:
2652:
2647:
2629:
2627:
2626:
2621:
2619:
2618:
2596:
2594:
2593:
2588:
2586:
2585:
2574:
2561:
2559:
2558:
2555:{\displaystyle }
2553:
2505:
2503:
2502:
2497:
2495:
2494:
2489:
2473:
2471:
2470:
2467:{\displaystyle }
2465:
2429:
2427:
2426:
2421:
2416:
2415:
2414:
2391:
2389:
2388:
2383:
2365:
2363:
2362:
2357:
2339:
2337:
2336:
2331:
2329:
2328:
2323:
2310:
2308:
2307:
2304:{\displaystyle }
2302:
2267:
2249:
2247:
2246:
2241:
2239:
2238:
2233:
2221:can be added to
2220:
2218:
2217:
2214:{\displaystyle }
2212:
2186:
2171:
2169:
2168:
2163:
2145:
2143:
2142:
2137:
2125:
2123:
2122:
2117:
2099:
2097:
2096:
2091:
2079:
2077:
2076:
2071:
2069:
2068:
2063:
2050:
2048:
2047:
2044:{\displaystyle }
2042:
2007:
1992:
1990:
1989:
1986:{\displaystyle }
1984:
1961:
1946:
1944:
1943:
1938:
1936:
1935:
1930:
1914:
1912:
1911:
1906:
1904:
1903:
1898:
1885:
1883:
1882:
1879:{\displaystyle }
1877:
1860:
1809:
1807:
1806:
1803:{\displaystyle }
1801:
1772:
1757:
1755:
1754:
1751:{\displaystyle }
1749:
1720:
1703:
1701:
1700:
1697:{\displaystyle }
1695:
1666:
1651:
1649:
1648:
1645:{\displaystyle }
1643:
1614:
1597:
1595:
1594:
1591:{\displaystyle }
1589:
1560:
1545:
1543:
1542:
1539:{\displaystyle }
1537:
1508:
1481:
1479:
1478:
1473:
1426:
1415:
1414:
1409:
1395:
1393:
1392:
1387:
1337:
1326:
1325:
1320:
1285:
1283:
1282:
1277:
1242:
1225:
1223:
1222:
1217:
1191:
1189:
1188:
1183:
1151:
1137:
1135:
1134:
1129:
1094:
1059:
1057:
1056:
1051:
1037:
1023:
1021:
1020:
1015:
1013:
1012:
1007:
998:
997:
992:
975:
973:
972:
967:
950:
933:
931:
930:
925:
911:
909:
908:
903:
886:
872:
870:
869:
864:
847:
817:
815:
814:
809:
781:
779:
778:
773:
771:
722:
720:
719:
714:
641:
639:
638:
633:
609:
594:
579:
577:
576:
571:
531:
529:
528:
523:
516:
510:
487:
485:
484:
479:
472:
466:
425:
423:
422:
417:
399:
397:
396:
391:
373:
371:
370:
365:
340:
338:
337:
332:
312:
304:
302:
301:
296:
289:
280:
258:
250:
248:
247:
242:
235:
229:
195:
193:
192:
187:
180:
174:
101:
99:
98:
93:
69:
67:
66:
61:
59:
56:
52:
46:
19:are a subset of
5485:
5484:
5480:
5479:
5478:
5476:
5475:
5474:
5455:
5454:
5453:
5452:
5433:
5406:
5387:
5352:
5337:
5333:
5326:
5312:
5297:
5260:
5256:
5225:
5221:
5190:
5186:
5158:
5152:
5148:
5141:
5123:
5110:
5103:
5089:
5085:
5080:
5053:
4983:
4980:
4979:
4916:
4913:
4912:
4894:
4889:
4888:
4886:
4883:
4882:
4821:
4818:
4817:
4799:
4794:
4793:
4791:
4788:
4787:
4726:
4723:
4722:
4704:
4699:
4698:
4696:
4693:
4692:
4631:
4628:
4627:
4609:
4604:
4603:
4601:
4598:
4597:
4519:
4516:
4515:
4509:
4478:
4474:
4462:
4458:
4446:
4442:
4436:
4432:
4430:
4427:
4426:
4377:
4374:
4373:
4354:
4349:
4348:
4346:
4343:
4342:
4290:
4287:
4286:
4243:
4240:
4239:
4221:
4216:
4215:
4213:
4210:
4209:
4159:
4156:
4155:
4104:
4101:
4100:
4057:
4054:
4053:
4035:
4030:
4029:
4027:
4024:
4023:
3973:
3970:
3969:
3921:
3918:
3917:
3863:
3860:
3859:
3816:
3813:
3812:
3794:
3789:
3788:
3786:
3783:
3782:
3732:
3729:
3728:
3680:
3677:
3676:
3615:
3612:
3611:
3593:
3588:
3587:
3585:
3582:
3581:
3543:
3540:
3539:
3506:
3505:
3501:
3496:
3493:
3492:
3459:
3458:
3454:
3449:
3446:
3445:
3412:
3411:
3407:
3402:
3399:
3398:
3353:
3352:
3348:
3343:
3340:
3339:
3335:. For example:
3319:
3314:
3313:
3311:
3308:
3307:
3267:
3264:
3263:
3241:
3236:
3235:
3233:
3230:
3229:
3228:, is added to
3189:
3186:
3185:
3163:
3160:
3159:
3137:
3134:
3133:
3116:
3111:
3110:
3108:
3105:
3104:
3052:
3049:
3048:
3028:
3023:
3022:
3020:
3017:
3016:
3015:, is added to
2973:
2970:
2969:
2947:
2944:
2943:
2921:
2918:
2917:
2900:
2895:
2894:
2892:
2889:
2888:
2839:
2836:
2835:
2818:
2813:
2812:
2810:
2807:
2806:
2766:
2763:
2762:
2742:
2737:
2736:
2734:
2731:
2730:
2687:
2684:
2683:
2661:
2658:
2657:
2635:
2632:
2631:
2614:
2610:
2602:
2599:
2598:
2575:
2570:
2569:
2567:
2564:
2563:
2511:
2508:
2507:
2490:
2485:
2484:
2482:
2479:
2478:
2435:
2432:
2431:
2407:
2406:
2402:
2397:
2394:
2393:
2371:
2368:
2367:
2345:
2342:
2341:
2324:
2319:
2318:
2316:
2313:
2312:
2263:
2258:
2255:
2254:
2234:
2229:
2228:
2226:
2223:
2222:
2182:
2177:
2174:
2173:
2151:
2148:
2147:
2131:
2128:
2127:
2105:
2102:
2101:
2085:
2082:
2081:
2064:
2059:
2058:
2056:
2053:
2052:
2003:
1998:
1995:
1994:
1957:
1952:
1949:
1948:
1931:
1926:
1925:
1923:
1920:
1919:
1899:
1894:
1893:
1891:
1888:
1887:
1856:
1845:
1842:
1841:
1836:
1832:
1825:
1819:
1768:
1763:
1760:
1759:
1716:
1711:
1708:
1707:
1662:
1657:
1654:
1653:
1610:
1605:
1602:
1601:
1556:
1551:
1548:
1547:
1504:
1499:
1496:
1495:
1489:
1422:
1410:
1405:
1404:
1402:
1399:
1398:
1333:
1321:
1316:
1315:
1313:
1310:
1309:
1304:
1297:
1238:
1236:
1233:
1232:
1199:
1196:
1195:
1147:
1145:
1142:
1141:
1090:
1088:
1085:
1084:
1066:
1033:
1031:
1028:
1027:
1008:
1003:
1002:
993:
988:
987:
985:
982:
981:
946:
944:
941:
940:
919:
916:
915:
882:
880:
877:
876:
843:
841:
838:
837:
791:
788:
787:
767:
765:
762:
761:
758:
741:
729:
684:
681:
680:
618:
615:
614:
556:
553:
552:
549:
499:
496:
495:
455:
452:
451:
433:
405:
402:
401:
379:
376:
375:
353:
350:
349:
320:
317:
316:
266:
263:
262:
218:
215:
214:
210:
163:
160:
159:
144:
139:
75:
72:
71:
45:
43:
40:
39:
25:formal grammars
12:
11:
5:
5483:
5473:
5472:
5467:
5451:
5450:
5404:
5350:
5331:
5324:
5295:
5254:
5235:(4): 263–278.
5219:
5184:
5146:
5139:
5108:
5101:
5082:
5081:
5079:
5076:
5075:
5074:
5069:
5064:
5059:
5052:
5049:
5032:
5029:
5026:
5023:
5020:
5017:
5014:
5011:
5008:
5005:
5002:
4999:
4996:
4993:
4990:
4987:
4974:
4973:
4962:
4959:
4956:
4953:
4950:
4947:
4944:
4941:
4938:
4935:
4932:
4929:
4926:
4923:
4920:
4910:
4897:
4892:
4879:
4878:
4867:
4864:
4861:
4858:
4855:
4852:
4849:
4846:
4843:
4840:
4837:
4834:
4831:
4828:
4825:
4815:
4802:
4797:
4784:
4783:
4772:
4769:
4766:
4763:
4760:
4757:
4754:
4751:
4748:
4745:
4742:
4739:
4736:
4733:
4730:
4720:
4707:
4702:
4689:
4688:
4677:
4674:
4671:
4668:
4665:
4662:
4659:
4656:
4653:
4650:
4647:
4644:
4641:
4638:
4635:
4625:
4612:
4607:
4594:
4593:
4590:
4568:
4565:
4562:
4559:
4556:
4553:
4550:
4547:
4544:
4541:
4538:
4535:
4532:
4529:
4526:
4523:
4508:
4505:
4492:
4489:
4486:
4481:
4477:
4473:
4470:
4465:
4461:
4457:
4454:
4449:
4445:
4439:
4435:
4414:
4411:
4408:
4405:
4402:
4399:
4396:
4393:
4390:
4387:
4384:
4381:
4362:
4357:
4352:
4337:
4336:
4324:
4321:
4318:
4315:
4312:
4309:
4306:
4303:
4300:
4297:
4294:
4274:
4271:
4268:
4265:
4262:
4259:
4256:
4253:
4250:
4247:
4237:
4224:
4219:
4206:
4205:
4193:
4190:
4187:
4184:
4181:
4178:
4175:
4172:
4169:
4166:
4163:
4144:
4141:
4138:
4135:
4132:
4129:
4126:
4123:
4120:
4117:
4114:
4111:
4108:
4088:
4085:
4082:
4079:
4076:
4073:
4070:
4067:
4064:
4061:
4051:
4038:
4033:
4020:
4019:
4007:
4004:
4001:
3998:
3995:
3992:
3989:
3986:
3983:
3980:
3977:
3958:
3955:
3952:
3949:
3946:
3943:
3940:
3937:
3934:
3931:
3928:
3925:
3906:
3903:
3900:
3897:
3894:
3891:
3888:
3885:
3882:
3879:
3876:
3873:
3870:
3867:
3847:
3844:
3841:
3838:
3835:
3832:
3829:
3826:
3823:
3820:
3810:
3797:
3792:
3779:
3778:
3766:
3763:
3760:
3757:
3754:
3751:
3748:
3745:
3742:
3739:
3736:
3717:
3714:
3711:
3708:
3705:
3702:
3699:
3696:
3693:
3690:
3687:
3684:
3664:
3661:
3658:
3655:
3652:
3649:
3646:
3643:
3640:
3637:
3634:
3631:
3628:
3625:
3622:
3619:
3609:
3596:
3591:
3578:
3577:
3574:
3565:
3564:
3553:
3550:
3547:
3536:
3535:
3524:
3521:
3518:
3512:
3509:
3504:
3500:
3489:
3488:
3477:
3474:
3471:
3465:
3462:
3457:
3453:
3442:
3441:
3430:
3427:
3424:
3418:
3415:
3410:
3406:
3395:
3394:
3383:
3380:
3377:
3374:
3371:
3368:
3365:
3359:
3356:
3351:
3347:
3322:
3317:
3295:
3292:
3289:
3286:
3283:
3280:
3277:
3274:
3271:
3259:
3258:
3244:
3239:
3217:
3214:
3211:
3208:
3205:
3202:
3199:
3196:
3193:
3184:; the string,
3173:
3170:
3167:
3147:
3144:
3141:
3119:
3114:
3092:
3089:
3086:
3083:
3080:
3077:
3074:
3071:
3068:
3065:
3062:
3059:
3056:
3047:If the items,
3045:
3031:
3026:
3004:
3001:
2998:
2995:
2992:
2989:
2986:
2983:
2980:
2977:
2968:; the string,
2957:
2954:
2951:
2931:
2928:
2925:
2903:
2898:
2876:
2873:
2870:
2867:
2864:
2861:
2858:
2855:
2852:
2849:
2846:
2843:
2821:
2816:
2794:
2791:
2788:
2785:
2782:
2779:
2776:
2773:
2770:
2759:
2745:
2740:
2718:
2715:
2712:
2709:
2706:
2703:
2700:
2697:
2694:
2691:
2671:
2668:
2665:
2645:
2642:
2639:
2617:
2613:
2609:
2606:
2584:
2581:
2578:
2573:
2551:
2548:
2545:
2542:
2539:
2536:
2533:
2530:
2527:
2524:
2521:
2518:
2515:
2493:
2488:
2475:
2463:
2460:
2457:
2454:
2451:
2448:
2445:
2442:
2439:
2419:
2413:
2410:
2405:
2401:
2381:
2378:
2375:
2355:
2352:
2349:
2327:
2322:
2300:
2297:
2294:
2291:
2288:
2285:
2282:
2279:
2276:
2273:
2270:
2266:
2262:
2253:If all items,
2251:
2237:
2232:
2210:
2207:
2204:
2201:
2198:
2195:
2192:
2189:
2185:
2181:
2161:
2158:
2155:
2135:
2115:
2112:
2109:
2089:
2067:
2062:
2040:
2037:
2034:
2031:
2028:
2025:
2022:
2019:
2016:
2013:
2010:
2006:
2002:
1982:
1979:
1976:
1973:
1970:
1967:
1964:
1960:
1956:
1934:
1929:
1916:
1902:
1897:
1875:
1872:
1869:
1866:
1863:
1859:
1855:
1852:
1849:
1831:
1828:
1823:
1818:
1815:
1799:
1796:
1793:
1790:
1787:
1784:
1781:
1778:
1775:
1771:
1767:
1747:
1744:
1741:
1738:
1735:
1732:
1729:
1726:
1723:
1719:
1715:
1693:
1690:
1687:
1684:
1681:
1678:
1675:
1672:
1669:
1665:
1661:
1641:
1638:
1635:
1632:
1629:
1626:
1623:
1620:
1617:
1613:
1609:
1587:
1584:
1581:
1578:
1575:
1572:
1569:
1566:
1563:
1559:
1555:
1535:
1532:
1529:
1526:
1523:
1520:
1517:
1514:
1511:
1507:
1503:
1487:
1471:
1468:
1465:
1462:
1459:
1456:
1453:
1450:
1447:
1444:
1441:
1438:
1435:
1432:
1429:
1425:
1421:
1418:
1413:
1408:
1385:
1382:
1379:
1376:
1373:
1370:
1367:
1364:
1361:
1358:
1355:
1352:
1349:
1346:
1343:
1340:
1336:
1332:
1329:
1324:
1319:
1302:
1295:
1275:
1272:
1269:
1266:
1263:
1260:
1257:
1254:
1251:
1248:
1245:
1241:
1215:
1212:
1209:
1206:
1203:
1181:
1178:
1175:
1172:
1169:
1166:
1163:
1160:
1157:
1154:
1150:
1127:
1124:
1121:
1118:
1115:
1112:
1109:
1106:
1103:
1100:
1097:
1093:
1081:
1080:
1077:
1074:
1065:
1062:
1049:
1046:
1043:
1040:
1036:
1011:
1006:
1001:
996:
991:
965:
962:
959:
956:
953:
949:
923:
901:
898:
895:
892:
889:
885:
862:
859:
856:
853:
850:
846:
834:
833:
830:
827:
807:
804:
801:
798:
795:
770:
757:
754:
740:
737:
728:
725:
712:
709:
706:
703:
700:
697:
694:
691:
688:
675:A traditional
666:John screamed
631:
628:
625:
622:
569:
566:
563:
560:
548:
545:
521:
515:
509:
506:
503:
477:
471:
465:
462:
459:
432:
429:
415:
412:
409:
389:
386:
383:
363:
360:
357:
330:
327:
324:
294:
288:
285:
279:
276:
273:
270:
240:
234:
228:
225:
222:
209:
206:
185:
179:
173:
170:
167:
143:
140:
138:
135:
91:
88:
85:
82:
79:
51:
17:ID/LP Grammars
9:
6:
4:
3:
2:
5482:
5471:
5468:
5466:
5463:
5462:
5460:
5446:
5442:
5438:
5431:
5429:
5427:
5425:
5423:
5421:
5419:
5417:
5415:
5413:
5411:
5409:
5400:
5396:
5392:
5385:
5383:
5381:
5379:
5377:
5375:
5373:
5371:
5369:
5367:
5365:
5363:
5361:
5359:
5357:
5355:
5348:
5344:
5342:
5335:
5327:
5325:1-85728-217-5
5321:
5317:
5310:
5308:
5306:
5304:
5302:
5300:
5291:
5287:
5282:
5277:
5273:
5269:
5265:
5258:
5250:
5246:
5242:
5238:
5234:
5230:
5223:
5215:
5211:
5207:
5203:
5199:
5195:
5188:
5180:
5176:
5172:
5168:
5164:
5157:
5150:
5142:
5140:0-674-34455-3
5136:
5131:
5130:
5121:
5119:
5117:
5115:
5113:
5104:
5098:
5094:
5087:
5083:
5073:
5072:Earley Parser
5070:
5068:
5065:
5063:
5060:
5058:
5055:
5054:
5048:
5044:
5030:
5024:
5021:
5015:
5012:
5009:
5006:
5003:
5000:
4997:
4994:
4991:
4988:
4957:
4954:
4948:
4945:
4942:
4939:
4936:
4933:
4930:
4927:
4924:
4921:
4911:
4895:
4881:
4880:
4862:
4859:
4853:
4850:
4847:
4844:
4841:
4838:
4835:
4832:
4829:
4826:
4816:
4800:
4786:
4785:
4767:
4764:
4758:
4755:
4752:
4749:
4746:
4743:
4740:
4737:
4734:
4731:
4721:
4705:
4691:
4690:
4672:
4669:
4663:
4660:
4657:
4654:
4651:
4648:
4645:
4642:
4639:
4636:
4626:
4610:
4596:
4595:
4591:
4588:
4587:
4581:
4579:
4566:
4560:
4557:
4551:
4548:
4545:
4542:
4539:
4533:
4530:
4527:
4524:
4504:
4484:
4479:
4468:
4463:
4452:
4447:
4437:
4412:
4406:
4403:
4397:
4394:
4391:
4388:
4385:
4382:
4360:
4355:
4335:
4319:
4316:
4310:
4307:
4304:
4301:
4298:
4295:
4272:
4266:
4263:
4257:
4254:
4251:
4248:
4238:
4222:
4208:
4207:
4204:
4188:
4185:
4179:
4173:
4170:
4167:
4164:
4142:
4136:
4133:
4127:
4121:
4118:
4115:
4112:
4109:
4086:
4080:
4077:
4071:
4068:
4065:
4062:
4052:
4036:
4022:
4021:
4018:
4002:
3999:
3993:
3987:
3984:
3981:
3978:
3956:
3950:
3947:
3941:
3935:
3932:
3929:
3926:
3904:
3898:
3895:
3889:
3886:
3883:
3877:
3874:
3871:
3868:
3845:
3839:
3836:
3830:
3827:
3824:
3821:
3811:
3795:
3781:
3780:
3777:
3761:
3758:
3752:
3746:
3743:
3740:
3737:
3715:
3709:
3706:
3700:
3694:
3691:
3688:
3685:
3662:
3656:
3653:
3647:
3644:
3641:
3638:
3635:
3629:
3626:
3623:
3620:
3610:
3594:
3580:
3579:
3575:
3572:
3571:
3551:
3548:
3545:
3538:
3537:
3519:
3498:
3491:
3490:
3472:
3451:
3444:
3443:
3425:
3404:
3397:
3396:
3378:
3375:
3372:
3369:
3366:
3345:
3338:
3337:
3336:
3320:
3290:
3287:
3284:
3281:
3278:
3275:
3272:
3242:
3212:
3209:
3206:
3203:
3200:
3197:
3194:
3171:
3168:
3165:
3145:
3142:
3139:
3117:
3087:
3084:
3081:
3078:
3072:
3066:
3063:
3060:
3057:
3046:
3029:
2999:
2996:
2993:
2990:
2987:
2984:
2981:
2978:
2955:
2952:
2949:
2929:
2926:
2923:
2901:
2871:
2868:
2865:
2862:
2856:
2850:
2847:
2844:
2819:
2789:
2786:
2783:
2780:
2777:
2774:
2771:
2760:
2743:
2713:
2710:
2707:
2704:
2701:
2698:
2695:
2692:
2669:
2666:
2663:
2643:
2640:
2637:
2615:
2611:
2607:
2604:
2582:
2579:
2576:
2546:
2543:
2540:
2537:
2531:
2525:
2522:
2519:
2516:
2491:
2476:
2458:
2455:
2452:
2449:
2446:
2443:
2440:
2417:
2399:
2379:
2376:
2373:
2353:
2350:
2347:
2325:
2295:
2292:
2289:
2286:
2280:
2274:
2271:
2268:
2252:
2235:
2205:
2202:
2199:
2196:
2193:
2190:
2187:
2159:
2156:
2153:
2133:
2113:
2110:
2107:
2087:
2065:
2035:
2032:
2029:
2026:
2020:
2014:
2011:
2008:
1977:
1974:
1971:
1968:
1965:
1962:
1932:
1917:
1900:
1870:
1867:
1864:
1861:
1853:
1850:
1839:
1838:
1837:
1827:
1814:
1810:
1794:
1791:
1788:
1785:
1782:
1779:
1776:
1742:
1739:
1736:
1733:
1730:
1727:
1724:
1704:
1688:
1685:
1682:
1679:
1676:
1673:
1670:
1636:
1633:
1630:
1627:
1624:
1621:
1618:
1598:
1582:
1579:
1576:
1573:
1570:
1567:
1564:
1530:
1527:
1524:
1521:
1518:
1515:
1512:
1492:
1490:
1482:
1466:
1463:
1457:
1454:
1451:
1448:
1445:
1439:
1433:
1416:
1411:
1396:
1380:
1377:
1371:
1368:
1365:
1362:
1359:
1356:
1353:
1347:
1327:
1322:
1307:
1305:
1298:
1291:
1286:
1267:
1261:
1258:
1255:
1252:
1249:
1229:
1228:
1210:
1207:
1204:
1194:
1176:
1173:
1170:
1164:
1158:
1138:
1122:
1119:
1116:
1113:
1110:
1104:
1078:
1075:
1072:
1071:
1070:
1061:
1047:
1044:
1041:
1024:
1009:
999:
994:
979:
976:
963:
960:
957:
954:
937:
936:
921:
914:
899:
896:
893:
890:
873:
860:
857:
854:
851:
831:
828:
825:
824:
823:
821:
805:
802:
799:
796:
793:
785:
753:
751:
747:
746:Earley Parser
736:
734:
733:Earley Parser
724:
710:
707:
704:
701:
698:
695:
689:
686:
678:
672:
671:
669:
664:
662:
655:
651:
649:
645:
629:
626:
623:
620:
610:
608:
601:
600:
595:
593:
587:
586:
581:
567:
564:
561:
558:
544:
542:
538:
532:
519:
513:
507:
501:
494:
488:
475:
469:
463:
457:
450:
445:
442:
441:local subtree
438:
428:
413:
410:
407:
387:
384:
381:
361:
358:
355:
347:
342:
328:
325:
322:
313:
311:
306:
292:
286:
283:
277:
274:
268:
259:
257:
252:
238:
232:
226:
220:
201:
197:
183:
177:
171:
165:
157:
152:
149:
134:
132:
127:
122:
120:
116:
112:
108:
103:
89:
86:
83:
80:
77:
36:
34:
30:
26:
22:
18:
5444:
5440:
5398:
5394:
5339:
5334:
5315:
5271:
5267:
5257:
5232:
5228:
5222:
5197:
5193:
5187:
5162:
5149:
5128:
5092:
5086:
5045:
4977:
4513:
4510:
4340:
4285:
4099:
3858:
3675:
3260:
1833:
1820:
1811:
1705:
1599:
1493:
1485:
1483:
1397:
1308:
1300:
1293:
1287:
1230:
1226:
1192:
1139:
1082:
1067:
1025:
980:
977:
938:
934:
912:
874:
835:
783:
759:
742:
730:
674:
667:
665:
660:
658:
657:
654:grammatical.
652:
612:
604:
598:
597:
589:
584:
583:
550:
540:
536:
534:
492:
491:
448:
447:
434:
427:precedence.
343:
314:
307:
260:
253:
211:
156:context free
153:
145:
123:
117:, and other
104:
37:
16:
15:
5200:(1): 1–21.
4514:Table 1.0,
2834:and items,
2392:and all of
1290:Permutation
5459:Categories
5102:9070176521
5078:References
4584:Table 2.0
3573:Set Lists
3568:Table 1.0
2761:If items,
2597:and where
782:stand for
648:complement
148:parse tree
5249:122866773
5214:144566546
5019:∅
5016:⋅
4952:∅
4949:⋅
4857:∅
4848:⋅
4762:∅
4741:⋅
4667:∅
4652:⋅
4589:Set List
4401:∅
4314:∅
4261:∅
4075:∅
3834:∅
3549:≺
3503:⟶
3456:⟶
3409:⟶
3350:⟶
3285:θ
3279:α
3207:λ
3172:β
3146:β
3143:⊀
3082:β
3079:∪
3064:α
2994:β
2985:α
2956:β
2930:β
2927:⊀
2866:β
2863:∪
2851:α
2784:θ
2778:λ
2708:β
2699:α
2670:β
2644:β
2641:⊀
2580:−
2541:β
2538:∪
2523:α
2453:λ
2418:λ
2404:⟶
2380:β
2354:β
2351:⊀
2290:β
2287:∪
2272:α
2200:β
2191:α
2160:β
2134:β
2114:β
2111:⊀
2088:β
2030:β
2027:∪
2012:α
1972:θ
1966:λ
1865:β
1774:⟶
1722:⟶
1668:⟶
1616:⟶
1562:⟶
1510:⟶
1440:⋅
1428:⟶
1348:⋅
1339:⟶
1268:⋅
1262:ι
1256:β
1250:α
1244:⟶
1211:ι
1205:β
1177:ι
1171:β
1165:⋅
1159:α
1153:⟶
1123:ι
1117:β
1111:α
1105:⋅
1096:⟶
1048:ι
1045:β
1042:α
1039:⟶
1000:…
964:⋅
961:ι
958:β
955:α
952:⟶
922:β
900:ι
897:β
894:⋅
891:α
888:⟶
861:ι
858:β
855:α
852:⋅
849:⟶
806:ι
800:β
794:α
693:→
663:screamed.
624:≺
562:≺
505:→
461:→
411:≺
385:≺
359:≺
326:≺
272:→
224:→
169:→
84:≺
50:⟶
5290:21824178
5179:17009554
5051:See also
3169:∉
2953:∉
2667:∉
2377:∉
2157:∉
668:suddenly
661:suddenly
5067:Parsing
2340:, then
1822:→
1484:string
677:PS rule
400:, then
5322:
5288:
5247:
5212:
5177:
5137:
5099:
4592:Items
3576:Items
3158:, and
3132:where
2942:, and
2916:where
2366:, and
517:
511:
473:
467:
437:string
435:For a
290:
281:
236:
230:
181:
175:
5245:S2CID
5210:S2CID
5175:S2CID
5159:(PDF)
2729:, to
2051:, of
1140:(2)
1083:(1)
875:(2)
836:(1)
784:start
659:John
158:rule
131:Merge
5320:ISBN
5286:PMID
5135:ISBN
5097:ISBN
2656:and
1758:(6)
1706:(3)
1652:(5)
1600:(2)
1546:(4)
1494:(1)
1231:(3)
939:(3)
786:and
644:head
374:and
344:The
5276:doi
5237:doi
5202:doi
5167:doi
541:(2)
537:(1)
493:(2)
449:(1)
5461::
5443:.
5439:.
5407:^
5399:11
5397:.
5393:.
5353:^
5298:^
5284:.
5272:35
5270:.
5266:.
5243:.
5231:.
5208:.
5198:15
5196:.
5173:.
5165:.
5161:.
5111:^
4503:.
2630:,
2146:,
1947:,
1824:ID
121:.
113:,
57:VP
53:NP
35:.
5445:7
5343:.
5328:.
5292:.
5278::
5251:.
5239::
5233:7
5216:.
5204::
5181:.
5169::
5143:.
5105:.
5031:,
5028:]
5025:0
5022:,
5013:F
5010:,
5007:D
5004:,
5001:C
4998:,
4995:T
4992:,
4989:S
4986:[
4961:]
4958:0
4955:,
4946:F
4943:,
4940:D
4937:,
4934:C
4931:,
4928:T
4925:,
4922:S
4919:[
4896:3
4891:I
4866:]
4863:0
4860:,
4854:,
4851:F
4845:d
4842:,
4839:C
4836:,
4833:T
4830:,
4827:S
4824:[
4801:2
4796:I
4771:]
4768:0
4765:,
4759:,
4756:f
4753:,
4750:d
4747:,
4744:c
4738:T
4735:,
4732:S
4729:[
4706:1
4701:I
4676:]
4673:0
4670:,
4664:,
4661:f
4658:,
4655:d
4649:C
4646:,
4643:T
4640:,
4637:S
4634:[
4611:0
4606:I
4567:,
4564:]
4561:0
4558:,
4555:}
4552:F
4549:,
4546:D
4543:,
4540:C
4537:{
4534:,
4531:T
4528:,
4525:S
4522:[
4491:]
4488:]
4485:f
4480:F
4476:[
4472:]
4469:d
4464:D
4460:[
4456:]
4453:c
4448:C
4444:[
4438:S
4434:[
4413:,
4410:]
4407:0
4404:,
4398:,
4395:F
4392:D
4389:C
4386:,
4383:S
4380:[
4361:,
4356:3
4351:I
4323:]
4320:0
4317:,
4311:,
4308:F
4305:D
4302:C
4299:,
4296:S
4293:[
4273:,
4270:]
4267:2
4264:,
4258:,
4255:d
4252:,
4249:D
4246:[
4223:3
4218:I
4192:]
4189:2
4186:,
4183:}
4180:d
4177:{
4174:,
4171:T
4168:,
4165:D
4162:[
4143:,
4140:]
4137:0
4134:,
4131:}
4128:D
4125:{
4122:,
4119:F
4116:C
4113:,
4110:S
4107:[
4087:,
4084:]
4081:1
4078:,
4072:,
4069:f
4066:,
4063:F
4060:[
4037:2
4032:I
4006:]
4003:1
4000:,
3997:}
3994:f
3991:{
3988:,
3985:T
3982:,
3979:F
3976:[
3957:,
3954:]
3951:1
3948:,
3945:}
3942:d
3939:{
3936:,
3933:T
3930:,
3927:D
3924:[
3905:,
3902:]
3899:0
3896:,
3893:}
3890:F
3887:,
3884:D
3881:{
3878:,
3875:C
3872:,
3869:S
3866:[
3846:,
3843:]
3840:0
3837:,
3831:,
3828:c
3825:,
3822:C
3819:[
3796:1
3791:I
3765:]
3762:0
3759:,
3756:}
3753:f
3750:{
3747:,
3744:T
3741:,
3738:F
3735:[
3716:,
3713:]
3710:0
3707:,
3704:}
3701:c
3698:{
3695:,
3692:T
3689:,
3686:C
3683:[
3663:,
3660:]
3657:0
3654:,
3651:}
3648:F
3645:,
3642:D
3639:,
3636:C
3633:{
3630:,
3627:T
3624:,
3621:S
3618:[
3595:0
3590:I
3552:D
3546:C
3523:}
3520:f
3517:{
3511:D
3508:I
3499:F
3476:}
3473:d
3470:{
3464:D
3461:I
3452:D
3429:}
3426:c
3423:{
3417:D
3414:I
3405:C
3382:}
3379:F
3376:,
3373:D
3370:,
3367:C
3364:{
3358:D
3355:I
3346:S
3321:n
3316:I
3294:]
3291:0
3288:,
3282:,
3276:,
3273:S
3270:[
3257:.
3243:n
3238:I
3216:]
3213:n
3210:,
3204:,
3201:T
3198:,
3195:Z
3192:[
3166:Z
3140:Z
3118:n
3113:I
3091:]
3088:i
3085:,
3076:}
3073:Z
3070:{
3067:,
3061:,
3058:A
3055:[
3044:.
3030:n
3025:I
3003:]
3000:k
2997:,
2991:,
2988:Z
2982:,
2979:A
2976:[
2950:Z
2924:Z
2902:i
2897:I
2875:]
2872:k
2869:,
2860:}
2857:Z
2854:{
2848:,
2845:A
2842:[
2820:n
2815:I
2793:]
2790:i
2787:,
2781:,
2775:,
2772:Z
2769:[
2758:.
2744:n
2739:I
2717:]
2714:i
2711:,
2705:,
2702:q
2696:,
2693:A
2690:[
2664:q
2638:q
2616:n
2612:q
2608:=
2605:q
2583:1
2577:n
2572:I
2550:]
2547:i
2544:,
2535:}
2532:q
2529:{
2526:,
2520:,
2517:A
2514:[
2492:n
2487:I
2474:.
2462:]
2459:0
2456:,
2450:,
2447:T
2444:,
2441:Z
2438:[
2412:D
2409:I
2400:Z
2374:Z
2348:Z
2326:0
2321:I
2299:]
2296:0
2293:,
2284:}
2281:Z
2278:{
2275:,
2269:,
2265:A
2261:[
2250:.
2236:0
2231:I
2209:]
2206:0
2203:,
2197:,
2194:Z
2188:,
2184:A
2180:[
2154:Z
2108:Z
2100:,
2066:0
2061:I
2039:]
2036:0
2033:,
2024:}
2021:Z
2018:{
2015:,
2009:,
2005:A
2001:[
1981:]
1978:0
1975:,
1969:,
1963:,
1959:Z
1955:[
1933:0
1928:I
1915:.
1901:0
1896:I
1874:]
1871:0
1868:,
1862:,
1858:T
1854:,
1851:S
1848:[
1798:]
1795:0
1792:,
1789:v
1786:z
1783:w
1780:.
1777:t
1770:X
1766:[
1746:]
1743:0
1740:,
1737:v
1734:w
1731:z
1728:.
1725:t
1718:X
1714:[
1692:]
1689:0
1686:,
1683:z
1680:v
1677:w
1674:.
1671:t
1664:X
1660:[
1640:]
1637:0
1634:,
1631:w
1628:z
1625:v
1622:.
1619:t
1612:X
1608:[
1586:]
1583:0
1580:,
1577:w
1574:v
1571:z
1568:.
1565:t
1558:X
1554:[
1534:]
1531:0
1528:,
1525:z
1522:w
1519:v
1516:.
1513:t
1506:X
1502:[
1488:1
1486:X
1470:]
1467:0
1464:,
1461:}
1458:z
1455:,
1452:w
1449:,
1446:v
1443:{
1437:}
1434:t
1431:{
1424:X
1420:[
1417::
1412:1
1407:X
1384:]
1381:0
1378:,
1375:}
1372:z
1369:,
1366:w
1363:,
1360:v
1357:,
1354:t
1351:{
1345:}
1342:{
1335:X
1331:[
1328::
1323:0
1318:X
1303:1
1301:X
1296:0
1294:X
1274:}
1271:{
1265:}
1259:,
1253:,
1247:{
1240:X
1214:}
1208:,
1202:{
1193:(
1180:}
1174:,
1168:{
1162:}
1156:{
1149:X
1126:}
1120:,
1114:,
1108:{
1102:}
1099:{
1092:X
1035:X
1010:n
1005:I
995:0
990:I
948:X
913:(
884:X
845:X
803:,
797:,
769:X
711:P
708:v
705:d
702:A
699:,
696:V
690:P
687:V
670:.
630:P
627:Y
621:X
568:P
565:D
559:V
520:A
514:C
508:D
502:B
476:D
470:C
464:B
458:A
414:D
408:B
388:D
382:C
362:C
356:B
329:C
323:B
293:D
287:,
284:C
278:,
275:B
269:A
239:D
233:C
227:B
221:A
184:D
178:C
172:B
166:A
90:P
87:V
81:P
78:N
47:S
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
