Repository: lark-parser/lark

Issue:
Indenter doesn't work intuitively with ignored tokens
**Describe the bug**

Indenter is cited as the way to parse whitespace-sensitive languages, but it has unintiutive and obtrusive behavior when there is an ignored token (ex a comment) in the middle of a newline sequence.

**To Reproduce**

Example:
```
GRAMMAR = r"""
	%import common.WS_INLINE
	%import common(C_COMMENT, CPP_COMMENT, SIGNED_NUMBER)

	%declare _INDENT _DEDENT
	%ignore WS_INLINE
	%ignore CPP_COMMENT
	%ignore C_COMMENT
	_NL: /(\r?\n[\t ]*)+/

	VARNAME: /[_a-zA-Z][_a-zA-Z0-9\/]*/

	start: [_NL] stmt*
	stmt: VARNAME _NL [_INDENT stmt+ _DEDENT]
"""

from lark import Lark
from lark.indenter import Indenter

class TreeIndenter(Indenter):
	NL_type = '_NL'
	OPEN_PAREN_types = []
	CLOSE_PAREN_types = []
	INDENT_type = '_INDENT'
	DEDENT_type = '_DEDENT'
	tab_len = 4

parser = Lark(GRAMMAR, postlex=TreeIndenter(), parser="lalr", start="start")
data = """
foo
bar
	/* */
	baz
"""
for tok in parser.lex(data):
	print(repr(tok))
print(parser.parse(data).pretty())
```

Remove the `/* */` from the `data` variable and it parses ok.

Happens because the ignored comment splits up the _NL tokens, and the indenter does not coalesce them.

Discussion:
@erezsh: The recommended solution is to capture comments in the newline.

Something like:

```lark
_NL: (NEWLINE | COMMENT)+
```

If you have a better way, we'll be happy to hear it.@ColonelThirtyTwo: @erezsh Thanks for the quick response. Looks like that works.

Might be worth putting that in the docs somewhere - seems like a gotcha. I think that the Indenter could be altered to coalesce adjacent _NL tokens too, so that the alteration isn't needed.@erezsh: I think you're right, it might be possible to do so. It would prevent languages in which a blank space is a dedent, but perhaps those aren't very common.

Anyway, in terms of performance, the current solution works best.

We can keep this issue open, while I consider the best option. If the code remains the same, I agree we should mention this somewhere in the docs.@MegaIng: @erezsh It might in general be worth considering creating a FAQs/best practices/common misunderstanding page.@erezsh: @MegaIng What would you put there? It doesn't seem like there are a lot of repetitive issues, since most of them are solved in the code.@MegaIng: Not necessarily repetitive (right now), but tricks that can't really be fixed and should be documented somewhere. Of course, we can just keep them in issues, but I think adding a page in the docs for them is worth it. #857 (which is actually a 'duplicate' of #517), #841, this issue, #838, #833, etc. (+ stuff from gitter, which is even less searchable than github issues). Most of them were just answered with a short text, explaining what is going on and how to fix the grammar. These could all just be formulated into a "FAQ" page. If you don't want this it's fine, but I think it is worth it.@erezsh: @MegaIng I have no objection. I you want to write such a page I'll add it.

Maybe some of those can fit in https://lark-parser.readthedocs.io/en/latest/how_to_use.html or https://lark-parser.readthedocs.io/en/latest/recipes.html@julie777: @erezsh 
> The recommended solution is to capture comments in the newline.
> 
> Something like:
> 
> ```lark
> _NL: (NEWLINE | COMMENT)+
> ```

That doesn't seem to work in my case where the comments are SH_COMMENTS because the comment eats the \n before NEWLINE sees it. 

Any suggestions for a grammar that
- uses SH or Python style comments
- uses indentation for structure and therefore uses Indenter



@erezsh: @julie777 That's what the official Python grammar does.. https://github.com/lark-parser/lark/blob/master/lark/grammars/python.lark@nchammas: I got tripped up by this same issue (comments confusing the indenter) and finding this thread helped me. 

I started by copying the [Parsing Indentation example][1] and worked from there, so updating the example -- specifically, [this comment][c] as well as [the `_NL` terminal][t] -- to incorporate the advice shared here would have saved me from this problem.

[c]: https://github.com/lark-parser/lark/blob/2f7c9a4e52ab82bbf1fd00699c79e8a6826fd9c4/examples/indented_tree.py#L11-L12
[t]: https://github.com/lark-parser/lark/blob/2f7c9a4e52ab82bbf1fd00699c79e8a6826fd9c4/examples/indented_tree.py#L27

Don't know if this would have also saved the other folks who ended up here, but I'm happy to submit a PR updating the example if the maintainers think it would help.

[1]: https://lark-parser.readthedocs.io/en/stable/examples/indented_tree.html@erezsh: If you think it would have saved you time, then it's worth adding / updating to the docs / examples.

I thought the python grammar is a sufficient example, but perhaps it's too long and complicated to extract insights from. And admittedly it's a non-obvious "trick",@nchammas: Since we added some documentation in #1502, shall we remove the "add to docs" tag from this issue and/or close it?@erezsh: SGTM

Solution patch:
diff --git a/.gitignore b/.gitignore
index 26275e4b..214e2d54 100644
--- a/.gitignore
+++ b/.gitignore
@@ -1,6 +1,7 @@
 *.pyc
 *.pyo
 /.tox
+/lark.egg-info/**
 /lark_parser.egg-info/**
 tags
 .vscode
@@ -12,3 +13,4 @@ tags
 /build
 docs/_build
 docs/examples
+docs/sg_execution_times.rst
diff --git a/docs/conf.py b/docs/conf.py
index aacf8bba..59c2ac6d 100644
--- a/docs/conf.py
+++ b/docs/conf.py
@@ -76,7 +76,7 @@
 #
 # This is also used if you do content translation via gettext catalogs.
 # Usually you set "language" from the command line for these cases.
-language = None
+language = 'en'
 
 # List of patterns, relative to source directory, that match files and
 # directories to ignore when looking for source files.
diff --git a/docs/how_to_develop.md b/docs/how_to_develop.md
index cf95fed0..a174c2e3 100644
--- a/docs/how_to_develop.md
+++ b/docs/how_to_develop.md
@@ -65,3 +65,15 @@ Another way to run the tests is using setup.py:
 ```bash
 python setup.py test
 ```
+
+## Building the Documentation
+
+To build the documentation:
+
+```sh
+cd docs/
+pip install -r requirements.txt
+make html
+```
+
+To review the result, open the built HTML files under `_build/html/` in your browser.
diff --git a/docs/recipes.md b/docs/recipes.md
index 8101e37c..b1e7a8b6 100644
--- a/docs/recipes.md
+++ b/docs/recipes.md
@@ -79,6 +79,7 @@ Prints out:
 
 *Note: We don't have to return a token, because comments are ignored*
 
+
 ## CollapseAmbiguities
 
 Parsing ambiguous texts with earley and `ambiguity='explicit'` produces a single tree with `_ambig` nodes to mark where the ambiguity occurred.
@@ -193,3 +194,13 @@ def parse_with_progress(parser: Lark, text: str, start=None):
 ```
 
 Keep in mind that this implementation relies on the `InteractiveParser` and, therefore, only works with the `LALR(1)` parser, and not `Earley`.
+
+
+## Parsing a Language with Significant Indentation
+
+If your grammar needs to support significant indentation (e.g. Python, YAML), you will need to use
+the `Indenter` class. Take a look at the [indented tree example][indent] as well as the
+[Python grammar][python] for inspiration.
+
+[indent]: examples/indented_tree.html
+[python]: https://github.com/lark-parser/lark/blob/master/lark/grammars/python.lark
diff --git a/examples/indented_tree.py b/examples/indented_tree.py
index 5ac928c7..a43733e4 100644
--- a/examples/indented_tree.py
+++ b/examples/indented_tree.py
@@ -3,28 +3,34 @@
 ===================
 
 A demonstration of parsing indentation (“whitespace significant” language)
-and the usage of the Indenter class.
+and the usage of the ``Indenter`` class.
 
 Since indentation is context-sensitive, a postlex stage is introduced to
-manufacture INDENT/DEDENT tokens.
+manufacture ``INDENT``/``DEDENT`` tokens.
 
-It is crucial for the indenter that the NL_type matches
-the spaces (and tabs) after the newline.
+It is crucial for the indenter that the ``NL_type`` matches the spaces (and
+tabs) after the newline.
+
+If your whitespace-significant grammar supports comments, then ``NL_type``
+must match those comments too. Otherwise, comments that appear in the middle
+of a line will `confuse Lark`_.
+
+.. _`confuse Lark`: https://github.com/lark-parser/lark/issues/863
 """
 from lark import Lark
 from lark.indenter import Indenter
 
 tree_grammar = r"""
-    ?start: _NL* tree
-
-    tree: NAME _NL [_INDENT tree+ _DEDENT]
-
     %import common.CNAME -> NAME
     %import common.WS_INLINE
-    %declare _INDENT _DEDENT
+    %import common.SH_COMMENT
     %ignore WS_INLINE
+    %ignore SH_COMMENT
+    %declare _INDENT _DEDENT
 
-    _NL: /(\r?\n[\t ]*)+/
+    ?start: _NL* tree
+    tree: NAME _NL [_INDENT tree+ _DEDENT]
+    _NL: (/\r?\n[\t ]*/ | SH_COMMENT)+
 """
 
 class TreeIndenter(Indenter):
@@ -39,6 +45,7 @@ class TreeIndenter(Indenter):
 
 test_tree = """
 a
+    # check this comment out
     b
     c
         d
diff --git a/lark/grammar.py b/lark/grammar.py
index 016496bd..3aa8e3ab 100644
--- a/lark/grammar.py
+++ b/lark/grammar.py
@@ -40,7 +40,7 @@ class Terminal(Symbol):
 
     is_term: ClassVar[bool] = True
 
-    def __init__(self, name, filter_out=False):
+    def __init__(self, name: str, filter_out: bool = False) -> None:
         self.name = name
         self.filter_out = filter_out
 
diff --git a/lark/tree.py b/lark/tree.py
index 76f8738e..9dccadd7 100644
--- a/lark/tree.py
+++ b/lark/tree.py
@@ -3,8 +3,10 @@
 
 from typing import List, Callable, Iterator, Union, Optional, Generic, TypeVar, TYPE_CHECKING
 
+from .lexer import Token
+
 if TYPE_CHECKING:
-    from .lexer import TerminalDef, Token
+    from .lexer import TerminalDef
     try:
         import rich
     except ImportError:
@@ -171,6 +173,16 @@ def find_data(self, data: str) -> 'Iterator[Tree[_Leaf_T]]':
 
 ###}
 
+    def find_token(self, token_type: str) -> Iterator[_Leaf_T]:
+        """Returns all tokens whose type equals the given token_type.
+
+        This is a recursive function that will find tokens in all the subtrees.
+
+        Example:
+            >>> term_tokens = tree.find_token('TERM')
+        """
+        return self.scan_values(lambda v: isinstance(v, Token) and v.type == token_type)
+
     def expand_kids_by_data(self, *data_values):
         """Expand (inline) children with any of the given data values. Returns True if anything changed"""
         changed = False


Test patch:
diff --git a/tests/test_trees.py b/tests/test_trees.py
index 1f69869e..55fdae91 100644
--- a/tests/test_trees.py
+++ b/tests/test_trees.py
@@ -17,6 +17,11 @@
 class TestTrees(TestCase):
     def setUp(self):
         self.tree1 = Tree('a', [Tree(x, y) for x, y in zip('bcd', 'xyz')])
+        self.tree2 = Tree('a', [
+            Tree('b', [Token('T', 'x')]),
+            Tree('c', [Token('T', 'y')]),
+            Tree('d', [Tree('z', [Token('T', 'zz'), Tree('zzz', 'zzz')])]),
+        ])
 
     def test_eq(self):
         assert self.tree1 == self.tree1
@@ -48,6 +53,11 @@ def test_iter_subtrees_topdown(self):
         nodes = list(self.tree1.iter_subtrees_topdown())
         self.assertEqual(nodes, expected)
 
+    def test_find_token(self):
+        expected = [Token('T', 'x'), Token('T', 'y'), Token('T', 'zz')]
+        tokens = list(self.tree2.find_token('T'))
+        self.assertEqual(tokens, expected)
+
     def test_visitor(self):
         class Visitor1(Visitor):
             def __init__(self):