153:
31:
89:
Terminal symbols are symbols that may appear in the outputs of the production rules of a formal grammar and which cannot be changed using the rules of the grammar. Applying the rules recursively to a source string of symbols will usually terminate in a final output string consisting only of terminal
187:
are those grammars in which the left-hand side of each production rule consists of only a single nonterminal symbol. This restriction is non-trivial; not all languages can be generated by context-free grammars. Those that can are called context-free languages. These are exactly the languages that
386:
177:, a designated member of the set of nonterminals from which all the strings in the language may be derived by successive applications of the production rules. In fact, the language defined by a grammar is precisely the set of
477:
symbol. That is, each production rule maps from one string of symbols to another, where the first string contains at least one nonterminal symbol. In the case that the body consists solely of the
574:
730:
691:
467:
595:
is a notation for expressing certain grammars. For instance, the following production rules in Backus-Naur form are used to represent an integer (which may be signed):
208:(or just 'productions') that specify which symbols may replace which other symbols; these rules may be used to generate strings, or to parse them. Each such rule has a
522:
416:
302:
825:
611:'0' | '1' | '2' | '3' | '4' | '5' | '6' | '7' | '8' | '9'
929:
893:
790:
This example supports strings with leading zeroes like "0056" or "0000", as well as negative zero strings like "-0" and "-00000".
160:
was formed by the grammar defined by the given production rules. This grammar can create strings with any number of the symbol Б
152:
205:
51:
752:
34:
The string "the dog ate the bone" was created using production rules that replaced non-terminal with terminal symbols.
535:
956:
951:
30:
581:
101:
is both a non-terminal symbol and the start symbol. The production rules for creating strings are as follows:
699:
216:, or right-hand side, which consists of a string that may replace it. Rules are often written in the form
133:
is a terminal symbol because no rule exists which would change it into something else. On the other hand,
433:
668:
193:
592:
862:
184:
909:
189:
921:
842:
427:
925:
889:
867:
762:
757:
913:
881:
834:
577:
501:
395:
39:
169:
Nonterminal symbols are those symbols that can be replaced. They may also be called simply
813:
Rosen, K. H. (2012). Discrete mathematics and its applications. McGraw-Hill. pages 847-851
138:
63:
914:
55:
381:{\displaystyle (\Sigma \cup N)^{*}N(\Sigma \cup N)^{*}\rightarrow (\Sigma \cup N)^{*}}
945:
275:
78:
846:
478:
244:
47:
145:
by a particular grammar is the set of strings that can be produced by the grammar
17:
419:
74:) are replaced by groups of terminal symbols according to the production rules.
212:, or left-hand side, which consists of the string that may be replaced, and a
838:
192:. Context-free languages are the theoretical basis for the syntax of most
149:. Diagram 1 illustrates a string that can be produced with this grammar.
823:
Chomsky, Noam (1956). "Three Models for the
Description of Language".
243:
In the classic formalization of generative grammars first proposed by
93:
Consider a grammar defined by two rules. In this grammar, the symbol
151:
77:
The terminals and nonterminals of a particular grammar are in two
29:
886:
Algebraic and automata theoretic properties of formal languages
920:. Reading, Mass.: Addison-Wesley Publishing Company. pp.
137:
has two rules that can change it, thus it is nonterminal. A
532:
A grammar is formally defined as the ordered quadruple
702:
671:
538:
504:
436:
398:
305:
481:, it may be denoted with a special notation (often
724:
685:
568:
516:
461:
410:
380:
569:{\displaystyle \langle N,\Sigma ,P,S\rangle }
8:
563:
539:
576:. Such a formal grammar is often called a
713:
703:
701:
672:
670:
537:
503:
453:
435:
402:
400:
397:
372:
347:
322:
304:
188:can be recognized by a non-deterministic
147:and that consist only of terminal symbols
27:Categories of symbols in formal grammars
806:
774:
916:Introduction to Formal Language Theory
826:IRE Transactions on Information Theory
725:{\displaystyle {\ce {A -> a | ab}}}
251:consists of the following components:
66:defined as part of a formal grammar.
469:represents zero or more symbols, and
7:
686:{\displaystyle {\ce {S -> cAd}}}
656:
652:
462:{\displaystyle (\Sigma \cup N)^{*}}
548:
440:
359:
334:
309:
62:are the elementary symbols of the
25:
181:strings that can be so derived.
44:terminal and nonterminal symbols
888:. North-Holland. pp. 8–9.
781:It contains no symbols at all.
714:
707:
676:
647:In this example, the symbols (
493:) in order to avoid confusion.
450:
437:
369:
356:
353:
344:
331:
319:
306:
173:. A formal grammar includes a
1:
735:In this example, the symbols
753:Alphabet (formal languages)
651:) are terminal symbols and
973:
659:are nonterminal symbols.
743:are nonterminal symbols.
739:are terminal symbols and
97:is a terminal symbol and
839:10.1109/TIT.1956.1056813
597:
582:phrase structure grammar
247:in the 1950s, a grammar
204:A grammar is defined by
79:completely separate sets
498:A distinguished symbol
293:, each rule of the form
50:used in specifying the
860:Chomsky, Noam (1957).
726:
687:
570:
518:
517:{\displaystyle S\in N}
463:
412:
411:{\displaystyle {}^{*}}
382:
161:
156:Diagram 1. The string
35:
727:
688:
649:-,0,1,2,3,4,5,6,7,8,9
571:
519:
464:
413:
383:
194:programming languages
185:Context-free grammars
155:
33:
910:Harrison, Michael A.
863:Syntactic Structures
700:
669:
662:Another example is:
536:
502:
434:
396:
303:
584:in the literature.
261:nonterminal symbols
236:can be replaced by
190:push down automaton
171:syntactic variables
165:Nonterminal symbols
72:syntactic variables
68:Nonterminal symbols
722:
683:
566:
514:
459:
408:
378:
162:
36:
18:Nonterminal symbol
882:Ginsburg, Seymour
763:Recursive grammar
758:Chomsky Hierarchy
720:
712:
706:
681:
675:
224:; e.g., the rule
16:(Redirected from
964:
957:Pattern matching
952:Formal languages
936:
935:
919:
906:
900:
899:
878:
872:
871:
857:
851:
850:
820:
814:
811:
791:
788:
782:
779:
742:
738:
731:
729:
728:
723:
721:
718:
717:
710:
704:
692:
690:
689:
684:
682:
679:
673:
658:
654:
650:
642:
639:
636:
632:
629:
626:
623:
620:
617:
614:
610:
607:
604:
601:
593:Backus–Naur form
578:rewriting system
575:
573:
572:
567:
523:
521:
520:
515:
492:
488:
484:
472:
468:
466:
465:
460:
458:
457:
425:
417:
415:
414:
409:
407:
406:
401:
387:
385:
384:
379:
377:
376:
352:
351:
327:
326:
291:production rules
288:
281:
272:terminal symbols
269:
258:
206:production rules
200:Production rules
159:
136:
132:
125:
121:
115:
112:
108:
100:
96:
85:Terminal symbols
60:Terminal symbols
52:production rules
48:lexical elements
40:formal languages
21:
972:
971:
967:
966:
965:
963:
962:
961:
942:
941:
940:
939:
932:
908:
907:
903:
896:
880:
879:
875:
859:
858:
854:
822:
821:
817:
812:
808:
803:
797:
795:
794:
789:
785:
780:
776:
771:
749:
740:
736:
698:
697:
667:
666:
657:<integer>
648:
645:
644:
640:
637:
634:
630:
627:
624:
621:
618:
615:
612:
608:
605:
602:
599:
590:
534:
533:
500:
499:
490:
486:
482:
470:
449:
432:
431:
423:
399:
394:
393:
368:
343:
318:
301:
300:
286:
279:
267:
256:
232:specifies that
202:
167:
157:
139:formal language
134:
130:
123:
119:
113:
110:
106:
98:
94:
87:
54:constituting a
28:
23:
22:
15:
12:
11:
5:
970:
968:
960:
959:
954:
944:
943:
938:
937:
930:
901:
894:
873:
852:
833:(3): 113–123.
815:
805:
804:
802:
799:
793:
792:
783:
773:
772:
770:
767:
766:
765:
760:
755:
748:
745:
733:
732:
716:
709:
694:
693:
678:
598:
589:
586:
565:
562:
559:
556:
553:
550:
547:
544:
541:
530:
529:
513:
510:
507:
495:
494:
456:
452:
448:
445:
442:
439:
405:
390:
389:
388:
375:
371:
367:
364:
361:
358:
355:
350:
346:
342:
339:
336:
333:
330:
325:
321:
317:
314:
311:
308:
295:
294:
283:
264:
201:
198:
166:
163:
127:
126:
116:
86:
83:
56:formal grammar
26:
24:
14:
13:
10:
9:
6:
4:
3:
2:
969:
958:
955:
953:
950:
949:
947:
933:
931:0-201-02955-3
927:
923:
918:
917:
911:
905:
902:
897:
895:0-7204-2506-9
891:
887:
883:
877:
874:
869:
866:. The Hague:
865:
864:
856:
853:
848:
844:
840:
836:
832:
828:
827:
819:
816:
810:
807:
800:
798:
787:
784:
778:
775:
768:
764:
761:
759:
756:
754:
751:
750:
746:
744:
696:
695:
665:
664:
663:
660:
653:<digit>
596:
594:
587:
585:
583:
579:
560:
557:
554:
551:
545:
542:
527:
511:
508:
505:
497:
496:
480:
476:
454:
446:
443:
429:
422:operator and
421:
403:
391:
373:
365:
362:
348:
340:
337:
328:
323:
315:
312:
299:
298:
297:
296:
292:
285:A finite set
284:
277:
273:
266:A finite set
265:
262:
255:A finite set
254:
253:
252:
250:
246:
241:
239:
235:
231:
227:
223:
219:
215:
211:
207:
199:
197:
195:
191:
186:
182:
180:
176:
172:
164:
154:
150:
148:
144:
140:
117:
104:
103:
102:
91:
84:
82:
80:
75:
73:
69:
65:
61:
57:
53:
49:
45:
41:
32:
19:
915:
904:
885:
876:
861:
855:
830:
824:
818:
809:
796:
786:
777:
734:
661:
646:
591:
531:
526:start symbol
525:
524:that is the
479:empty string
474:
290:
271:
260:
248:
245:Noam Chomsky
242:
237:
233:
229:
225:
221:
217:
213:
209:
203:
183:
178:
175:start symbol
174:
170:
168:
146:
142:
128:
92:
88:
76:
71:
67:
59:
43:
37:
475:nonterminal
420:Kleene star
141:defined or
122:can become
118:The symbol
109:can become
105:The symbol
946:Categories
801:References
473:means one
708:⟶
677:⟶
564:⟩
549:Σ
540:⟨
509:∈
455:∗
444:∪
441:Σ
428:set union
404:∗
374:∗
363:∪
360:Σ
354:→
349:∗
338:∪
335:Σ
324:∗
313:∪
310:Σ
143:generated
90:symbols.
912:(1978).
884:(1975).
847:19519474
747:See also
426:denotes
276:disjoint
274:that is
179:terminal
64:language
46:are the
737:a,b,c,d
616:integer
588:Example
424:∪
418:is the
158:Б Б Б Б
928:
892:
868:Mouton
845:
491:ε
483:Λ
392:where
268:Σ
843:S2CID
769:Notes
638:digit
628:digit
603:digit
580:or a
430:, so
278:from
129:Here
926:ISBN
890:ISBN
655:and
641:>
635:<
631:>
625:<
619:>
613:<
606:>
600:<
222:body
218:head
214:body
210:head
70:(or
835:doi
741:S,A
680:cAd
622:::=
609:::=
489:or
289:of
270:of
259:of
58:.
38:In
948::
924:.
922:13
841:.
829:.
719:ab
643:}
485:,
240:.
228:→
220:→
196:.
81:.
42:,
934:.
898:.
870:.
849:.
837::
831:2
715:|
711:a
705:A
674:S
633:{
561:S
558:,
555:P
552:,
546:,
543:N
528:.
512:N
506:S
487:e
471:N
451:)
447:N
438:(
370:)
366:N
357:(
345:)
341:N
332:(
329:N
320:)
316:N
307:(
287:P
282:.
280:N
263:.
257:N
249:G
238:b
234:a
230:b
226:a
135:Ψ
131:Б
124:Б
120:Ψ
114:Ψ
111:Б
107:Ψ
99:Ψ
95:Б
20:)
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
