Skip to main content
Top

2021 | OriginalPaper | Chapter

Context-Free Grammars with Lookahead

Authors : Takayuki Miyazaki, Yasuhiko Minamide

Published in: Language and Automata Theory and Applications

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

We introduce context-free grammars with lookahead. The grammars are an extension of both context-free grammars and parsing expression grammars, hence we can handle the two grammars in a unified way. To accommodate lookahead, we use a language with lookahead, which is a set of string pairs. We considered the grammar as a system of equations and give the language with lookahead by the limit of iterations from the empty set. The language class is closed under union, intersection, complement, and a weak version of concatenation and Kleene star.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Literature
3.
go back to reference Barash, M., Okhotin, A.: An extension of context-free grammars with one-sided context specifications. Inf. Comput. 237, 268–293 (2014)MathSciNetCrossRef Barash, M., Okhotin, A.: An extension of context-free grammars with one-sided context specifications. Inf. Comput. 237, 268–293 (2014)MathSciNetCrossRef
4.
go back to reference Barash, M., Okhotin, A.: Linear grammars with one-sided contexts and their automaton representation. RAIRO Theor. Inf. Appl. 49(2), 153–178 (2015)MathSciNetCrossRef Barash, M., Okhotin, A.: Linear grammars with one-sided contexts and their automaton representation. RAIRO Theor. Inf. Appl. 49(2), 153–178 (2015)MathSciNetCrossRef
6.
go back to reference Chida, N., Kuramitsu, K.: Parsing expression grammars with unordered choices. J. Inf. Process. 25, 975–982 (2017)MATH Chida, N., Kuramitsu, K.: Parsing expression grammars with unordered choices. J. Inf. Process. 25, 975–982 (2017)MATH
7.
go back to reference Chomsky, N., Schützenberger, M.: The algebraic theory of context-free languages. In: Computer Programming and Formal Systems, vol. 35, pp. 118–161. Elsevier (1963) Chomsky, N., Schützenberger, M.: The algebraic theory of context-free languages. In: Computer Programming and Formal Systems, vol. 35, pp. 118–161. Elsevier (1963)
8.
9.
go back to reference Ford, B.: Parsing expression grammars: a recognition-based syntactic foundation. In: Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 111–122. ACM (2004) Ford, B.: Parsing expression grammars: a recognition-based syntactic foundation. In: Proceedings of the 31st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pp. 111–122. ACM (2004)
10.
12.
go back to reference Mascarenhas, F., Medeiros, S., Ierusalimschy, R.: On the relation between context-free grammars and parsing expression grammars. Sci. Comput. Program. 89, 235–250 (2014)CrossRef Mascarenhas, F., Medeiros, S., Ierusalimschy, R.: On the relation between context-free grammars and parsing expression grammars. Sci. Comput. Program. 89, 235–250 (2014)CrossRef
13.
go back to reference Might, M., Darais, D., Spiewak, D.: Parsing with derivatives: a functional pearl. In: Proceedings of the 16th ACM SIGPLAN International Conference on Functional Programming, pp. 189–195. ACM (2011) Might, M., Darais, D., Spiewak, D.: Parsing with derivatives: a functional pearl. In: Proceedings of the 16th ACM SIGPLAN International Conference on Functional Programming, pp. 189–195. ACM (2011)
14.
go back to reference Miyazaki, T., Minamide, Y.: Derivatives of regular expressions with lookahead. J. Inf. Process. 27, 422–430 (2019) Miyazaki, T., Minamide, Y.: Derivatives of regular expressions with lookahead. J. Inf. Process. 27, 422–430 (2019)
15.
go back to reference Morihata, A.: Translation of regular expression with lookahead into finite state automaton. Comput. Softw. 29(1), 147–158 (2012) Morihata, A.: Translation of regular expression with lookahead into finite state automaton. Comput. Softw. 29(1), 147–158 (2012)
17.
go back to reference Parr, T., Fisher, K.: LL(*) the foundation of the ANTLR parser generator. In: Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 425–436 (2011) Parr, T., Fisher, K.: LL(*) the foundation of the ANTLR parser generator. In: Proceedings of the 32nd ACM SIGPLAN Conference on Programming Language Design and Implementation, pp. 425–436 (2011)
18.
go back to reference Sakuma, Y., Minamide, Y., Voronkov, A.: Translating regular expression matching into transducers. J. Appl. Logic 10(1), 32–51 (2012)MathSciNetCrossRef Sakuma, Y., Minamide, Y., Voronkov, A.: Translating regular expression matching into transducers. J. Appl. Logic 10(1), 32–51 (2012)MathSciNetCrossRef
19.
go back to reference Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time (preliminary report). In: Proceedings of the 5th Annual ACM Symposium on Theory of Computing, pp. 1–9. ACM (1973) Stockmeyer, L.J., Meyer, A.R.: Word problems requiring exponential time (preliminary report). In: Proceedings of the 5th Annual ACM Symposium on Theory of Computing, pp. 1–9. ACM (1973)
20.
go back to reference Vardi, M.Y.: The complexity of relational query languages. In: Proceedings of the 14th Annual ACM Symposium on Theory of Computing, pp. 137–146. ACM (1982) Vardi, M.Y.: The complexity of relational query languages. In: Proceedings of the 14th Annual ACM Symposium on Theory of Computing, pp. 137–146. ACM (1982)
Metadata
Title
Context-Free Grammars with Lookahead
Authors
Takayuki Miyazaki
Yasuhiko Minamide
Copyright Year
2021
DOI
https://doi.org/10.1007/978-3-030-68195-1_16

Premium Partner