ll1.ll1 3.4 KB

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576
  1. /*
  2. This is the grammar for LL1 itself. The lexer is the Go language scanner,
  3. so comments are ignored.
  4. */
  5. Grammar -> Rules `` .
  6. Rules -> Rule OptRules .
  7. OptRules -> '.' Rules | epsilon.
  8. Rule -> Name arrow Definition Template.
  9. Name -> identifier .
  10. Template -> rawString | epsilon .
  11. // Alternates consist of sequences.
  12. Definition -> Alternates .
  13. Alternates -> Sequence OptSequences .
  14. OptSequences -> '|' Alternates | epsilon.
  15. Sequence -> Element OptElements .
  16. OptElements -> Element OptElements | epsilon.
  17. Element -> Parenthesis .
  18. Element -> Name .
  19. Element -> literal /*| Rule */.
  20. Parenthesis -> '(' Definition ')' .
  21. // Lexer specifications. These are rules that have a name that
  22. // begins with a lower case letter
  23. dot -> '.' .
  24. or -> '|' .
  25. identifier -> ruleName | terminalName .
  26. ruleName -> "re:[[:isUpper:]][[:isAlNum]]" .
  27. terminalName -> "re:[[:isLower:]][[:isAlNum]]" .
  28. epsilon -> "epsilon" | 'ε' .
  29. arrow -> "->" | '→' .
  30. literal -> stringLiteral | charLiteral .
  31. stringLiteral -> "re:\"[^\"]+\"" .
  32. charLiteral -> "re:'[^']+'" .
  33. rawString -> "re:`[^`]+`/" .
  34. whiteSpace -> "re:[:isblank:]+" .
  35. lineComment -> "re://[^\n]\n" .
  36. handCoded -> "code:" `
  37. // Not implemented
  38. ` .
  39. /*
  40. Grammar identifier ∅ no yes
  41. Rules identifier ∅ no yes
  42. OptRules . ∅ yes yes
  43. Rule identifier . no yes
  44. Name identifier ) literal ( identifier | arrow . no yes
  45. Definition literal ( identifier ) . no yes
  46. Alternates literal ( identifier ) . no yes
  47. OptSequences | ) . yes yes
  48. Sequence literal ( identifier ) | . no yes
  49. OptElements literal ( identifier ) | . yes yes
  50. Element literal ( identifier ) literal ( identifier | . no yes
  51. Parenthesis ( ) literal ( identifier | . no yes
  52. Output of:
  53. ./ll1 ll1.ll1 -t ll1.template.debug | column -e -s '~' -t -x
  54. Rule Definition First Follow
  55. ---------------- ---------------- ---------------- ----------------
  56. Grammar (Rules) identifier $
  57. Rules (Rule OptRules) identifier $
  58. OptRules ("." Rules | ε) . ε $
  59. Rule (Name arrow Definition) identifier . ε
  60. Name (identifier) identifier ( arrow identifier literal ε
  61. Definition (Alternates) ( identifier literal ) . ε
  62. Alternates (Sequence OptSequences) ( identifier literal ) . ε
  63. OptSequences ("|" Alternates | ε) | ε ) . ε
  64. Sequence (Element OptElements) ( identifier literal | ε
  65. OptElements (Element OptElements | ε) ( identifier literal ε | ε
  66. Element (Parenthesis | Name | literal) ( identifier literal ( identifier literal ε
  67. Parenthesis ("(" Definition ")") ( ( identifier literal ε
  68. */