summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorEdward Z. Yang <ezyang@cs.stanford.edu>2016-12-20 23:38:20 -0800
committerEdward Z. Yang <ezyang@cs.stanford.edu>2016-12-21 08:56:44 -0800
commit46f7f31f3d81fce0790fed25d26e2fc6ac577378 (patch)
tree5aced60a165a0d6e80c7b199b14705db87e8fe20
parent99db12f54fa5d4dcf264f00c6f97d08d33b587d0 (diff)
downloadhaskell-46f7f31f3d81fce0790fed25d26e2fc6ac577378.tar.gz
Notes on parsing lists in Parser.y
Summary: Maybe everyone knows this but I think it is worth mentioning Signed-off-by: Edward Z. Yang <ezyang@cs.stanford.edu> Test Plan: none Reviewers: bgamari, austin Subscribers: thomie, mpickering Differential Revision: https://phabricator.haskell.org/D2890
-rw-r--r--compiler/parser/Parser.y44
1 files changed, 44 insertions, 0 deletions
diff --git a/compiler/parser/Parser.y b/compiler/parser/Parser.y
index 112c4a9b44..befd52fd7c 100644
--- a/compiler/parser/Parser.y
+++ b/compiler/parser/Parser.y
@@ -316,6 +316,48 @@ correctly, see the README in (REPO)/utils/check-api-annotations for details on
how to set up a test using the check-api-annotations utility, and interpret the
output it generates.
+Note [Parsing lists]
+---------------------
+You might be wondering why we spend so much effort encoding our lists this
+way:
+
+importdecls
+ : importdecls ';' importdecl
+ | importdecls ';'
+ | importdecl
+ | {- empty -}
+
+This might seem like an awfully roundabout way to declare a list; plus, to add
+insult to injury you have to reverse the results at the end. The answer is that
+left recursion prevents us from running out of stack space when parsing long
+sequences. See: https://www.haskell.org/happy/doc/html/sec-sequences.html for
+more guidance.
+
+By adding/removing branches, you can affect what lists are accepted. Here
+are the most common patterns, rewritten as regular expressions for clarity:
+
+ -- Equivalent to: ';'* (x ';'+)* x? (can be empty, permits leading/trailing semis)
+ xs : xs ';' x
+ | xs ';'
+ | x
+ | {- empty -}
+
+ -- Equivalent to x (';' x)* ';'* (non-empty, permits trailing semis)
+ xs : xs ';' x
+ | xs ';'
+ | x
+
+ -- Equivalent to ';'* alts (';' alts)* ';'* (non-empty, permits leading/trailing semis)
+ alts : alts1
+ | ';' alts
+ alts1 : alts1 ';' alt
+ | alts1 ';'
+ | alt
+
+ -- Equivalent to x (',' x)+ (non-empty, no trailing semis)
+ xs : x
+ | x ',' xs
+
-- -----------------------------------------------------------------------------
-}
@@ -665,6 +707,8 @@ body2 :: { ([AddAnn]
:(fst $2), snd $2) }
| missing_module_keyword top close { ([],snd $2) }
+
+
top :: { ([AddAnn]
,([LImportDecl RdrName], [LHsDecl RdrName])) }
: importdecls { (fst $1