Computational nanotechnology
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Comp. nanotechnol.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Computational nanotechnology, 2020, Volume 7, Issue 2, Pages 42–48
DOI: https://doi.org/10.33693/2313-223X-2020-7-2-42-48
(Mi cn298)
 

DEVELOPMENT OF THE ARCHITECTURE OF QUANTUM COMPUTERS BASED ON NEW PRINCIPLES, CREATING NEW QUANTUM PROGRAMMING

Deadlock algorithm for advanced syntactical analysis and its application to programming languages for quantum computers

V. V. Kishkana, K. V. Safonovb

a East Siberian College of Tourism and Service
b Reshetnev Siberian State University of Science and Technology
Abstract: When developing promising programming languages designed to support the work of supercomputers, including quantum ones, there is a need for research related to testing the developed language under conditions when parsers do not yet exist for it. In particular, in the process of developing a programming language for a quantum computer, it becomes necessary to parse a certain program written in a new programming language, which, like all programming languages, belongs to the class of context-free languages (cf-languages). The problem of syntactical analysis of the monomials of cf-languages was posed in the 50-60s of the last century, however, there are some discrepancies in its formulation, and therefore there is a need to clarify the formulation of this problem. In this regard, we will call the expanded problem of parsing the problem of developing a stupid (non-stop, irrevocable) algorithm that allows establishing whether a given monomial can be deduced using a system of products that form a cf-language grammar, and also find all the conclusions of this monomial at once if the latter exists. The description of the monomial inference is understood as follows: it is necessary to determine for which products from the grammar of the cf-language, how many times and in what order they are used to derive this monomial, which is equivalent to constructing all the output trees. The article has developed a deadlockless algorithm for solving the extended problem of parsing, based on the method of hierarchy of marked brackets. The marked brackets order shows what products they are assigned to, and allows you to trace the order of its use. The algorithm uses the method of successive approximations to solve the Chomsky-Schützenberger system of equations associated with the cf-language grammar. The developed algorithm has a simple software implementation; an assessment of the complexity of the algorithm is also given.
Keywords: syntactical analysis algorithm, quantum computer.
Received: 05.05.2020
Document Type: Article
UDC: 519.682
Language: Russian
Citation: V. V. Kishkan, K. V. Safonov, “Deadlock algorithm for advanced syntactical analysis and its application to programming languages for quantum computers”, Comp. nanotechnol., 7:2 (2020), 42–48
Citation in format AMSBIB
\Bibitem{KisSaf20}
\by V.~V.~Kishkan, K.~V.~Safonov
\paper Deadlock algorithm for advanced syntactical analysis and its application to programming languages for quantum computers
\jour Comp. nanotechnol.
\yr 2020
\vol 7
\issue 2
\pages 42--48
\mathnet{http://mi.mathnet.ru/cn298}
\crossref{https://doi.org/10.33693/2313-223X-2020-7-2-42-48}
Linking options:
  • https://www.mathnet.ru/eng/cn298
  • https://www.mathnet.ru/eng/cn/v7/i2/p42
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Computational nanotechnology
    Statistics & downloads:
    Abstract page:114
    Full-text PDF :18
    References:1
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024