Entire Site
Free Trial
Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.
- Create BookmarkCreate Bookmark
- Create Note or TagCreate Note or Tag
- DownloadDownload
- PrintPrint
Chapter 19. Parsing > Avoiding Backtracking
19.8. Avoiding Backtracking
Whenever an alternative p | q is parsed and p fails, the parser tries q on the same input. This backtracking can be inefficient. For example, consider an arithmetic expression parser with the rules
def expr: Parser[Any] = term ~ ("+" | "-") ~ expr | term
def term: Parser[Any] = factor ~ "*" ~ term | factor
def factor: Parser[Any] = "(" ~ expr ~ ")" | number
