XACC
parser.h
Go to the documentation of this file.
1 /*
2  * This file is part of Quantum++.
3  *
4  * MIT License
5  *
6  * Copyright (c) 2013 - 2020 Vlad Gheorghiu.
7  *
8  * Permission is hereby granted, free of charge, to any person obtaining a copy
9  * of this software and associated documentation files (the "Software"), to deal
10  * in the Software without restriction, including without limitation the rights
11  * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
12  * copies of the Software, and to permit persons to whom the Software is
13  * furnished to do so, subject to the following conditions:
14  *
15  * The above copyright notice and this permission notice shall be included in
16  * all copies or substantial portions of the Software.
17  *
18  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
19  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
20  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
21  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
22  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
23  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
24  * SOFTWARE.
25  *
26  * Adapted from Bruno Schmitt's Tweedledee library
27  */
28 
34 #ifndef QASM_PARSER_H_
35 #define QASM_PARSER_H_
36 
37 namespace qpp {
38 namespace qasm {
39 
45 class Parser {
46  Preprocessor& pp_lexer_;
47 
48  bool error_ = false;
49  bool supress_errors_ = false;
50  Token current_token_ = Token();
51  int bits_ = 0;
52  int qubits_ = 0;
53 
54  public:
60  Parser(Preprocessor& pp_lexer) : pp_lexer_(pp_lexer) {}
61 
67  std::unique_ptr<QCircuit> parse() {
68  // Parse the program
69  auto result = parse_program();
70  if (error_)
71  throw exception::ParseError("qpp::qasm::Parser::parse()");
72 
73  // Generate the QCircuit
74  return result.to_QCircuit();
75  }
76 
77  private:
83  void consume_token(bool reset = false) {
84  current_token_ = pp_lexer_.next_token();
85  if (reset)
86  supress_errors_ = false;
87  }
88 
99  Token expect_and_consume_token(Token::Kind expected) {
100  if (current_token_.is_not(expected)) {
101  error_ = true;
102  if (!supress_errors_) {
103  std::cerr << current_token_.location();
104  std::cerr << ": expected " << expected;
105  std::cerr << " but got " << current_token_.kind() << "\n";
106  ;
107  supress_errors_ = true;
108  }
109  return current_token_;
110  }
111 
112  auto return_token = current_token_;
113  consume_token();
114  return return_token;
115  }
116 
126  Token consume_until(Token::Kind expected) {
127  while (current_token_.is_not(expected) &&
128  current_token_.is_not(Token::Kind::eof)) {
129  error_ = true;
130  if (!supress_errors_) {
131  std::cerr << current_token_.location();
132  std::cerr << ": expected " << expected;
133  std::cerr << " but got " << current_token_.kind() << "\n";
134  ;
135  supress_errors_ = true;
136  }
137  consume_token();
138  }
139 
140  auto return_token = current_token_;
141  consume_token(true);
142  return return_token;
143  }
144 
154  bool try_and_consume_token(Token::Kind expected) {
155  if (current_token_.is_not(expected)) {
156  return false;
157  }
158  consume_token();
159  return true;
160  }
161 
177  QASM parse_program() {
178  std::vector<StatementPtr> ret;
179 
180  // The first (non-comment) line of an Open QASM program must be
181  // OPENQASM M.m; indicating a major version M and minor version m.
182  parse_header();
183 
184  while (!current_token_.is(Token::Kind::eof)) {
185  switch (current_token_.kind()) {
186  // Parse declarations (<decl>)
187  case Token::Kind::kw_creg:
188  ret.emplace_back(parse_reg_decl(false));
189  break;
190  case Token::Kind::kw_qreg:
191  ret.emplace_back(parse_reg_decl(true));
192  break;
193 
194  case Token::Kind::kw_gate:
195  ret.emplace_back(parse_gate_decl());
196  break;
197 
198  case Token::Kind::kw_opaque:
199  ret.emplace_back(parse_opaque_decl());
200  break;
201 
202  // Parse quantum operations (<qop>)
203  case Token::Kind::identifier:
204  case Token::Kind::kw_cx:
205  case Token::Kind::kw_measure:
206  case Token::Kind::kw_reset:
207  case Token::Kind::kw_u:
208  ret.emplace_back(parse_qop());
209  break;
210 
211  case Token::Kind::kw_barrier:
212  ret.emplace_back(parse_barrier());
213  break;
214 
215  case Token::Kind::kw_if:
216  ret.emplace_back(parse_if());
217  break;
218 
219  default:
220  error_ = true;
221  if (!supress_errors_) {
222  std::cerr << current_token_.location();
223  std::cerr << ": expected a declaration or statement";
224  std::cerr << " but got " << current_token_.kind()
225  << "\n";
226  ;
227  supress_errors_ = true;
228  }
229 
230  consume_until(Token::Kind::semicolon);
231  break;
232  }
233  }
234 
235  return QASM(bits_, qubits_, std::move(ret));
236  }
237 
243  void parse_header() {
244  consume_token();
245  expect_and_consume_token(Token::Kind::kw_openqasm);
246  expect_and_consume_token(Token::Kind::real);
247  consume_until(Token::Kind::semicolon);
248  }
249 
259  StatementPtr parse_reg_decl(bool quantum) {
260  auto loc = current_token_.location();
261 
262  consume_token();
263  auto identifier = expect_and_consume_token(Token::Kind::identifier);
264  expect_and_consume_token(Token::Kind::l_square);
265  auto size = expect_and_consume_token(Token::Kind::nninteger);
266  expect_and_consume_token(Token::Kind::r_square);
267  consume_until(Token::Kind::semicolon);
268 
269  quantum ? qubits_ += (int) size : bits_ += (int) size;
270  return StatementPtr(new RegisterDecl(loc, identifier, quantum, size));
271  }
272 
283  StatementPtr parse_gate_decl() {
284  auto loc = current_token_.location();
285 
286  consume_token();
287  auto identifier = expect_and_consume_token(Token::Kind::identifier);
288 
289  std::vector<ident> c_params;
290  if (try_and_consume_token(Token::Kind::l_paren)) {
291  c_params = parse_idlist();
292  expect_and_consume_token(Token::Kind::r_paren);
293  }
294 
295  auto q_params = parse_idlist();
296 
297  expect_and_consume_token(Token::Kind::l_brace);
298  std::vector<GatePtr> body;
299  if (!try_and_consume_token(Token::Kind::r_brace)) {
300  body = parse_goplist();
301  expect_and_consume_token(Token::Kind::r_brace);
302  }
303 
304  return StatementPtr(new GateDecl(loc, identifier, false, c_params,
305  q_params, std::move(body)));
306  }
307 
318  StatementPtr parse_opaque_decl() {
319  auto loc = current_token_.location();
320 
321  consume_token();
322  auto identifier = expect_and_consume_token(Token::Kind::identifier);
323 
324  std::vector<ident> c_params;
325  if (try_and_consume_token(Token::Kind::l_paren)) {
326  c_params = parse_idlist();
327  expect_and_consume_token(Token::Kind::r_paren);
328  }
329 
330  auto q_params = parse_idlist();
331 
332  return StatementPtr(
333  new GateDecl(loc, identifier, true, c_params, q_params, {}));
334  }
335 
345  std::vector<GatePtr> parse_goplist() {
346  std::vector<GatePtr> ret;
347  bool finished = false;
348 
349  while (!finished) {
350  switch (current_token_.kind()) {
351  case Token::Kind::kw_cx:
352  case Token::Kind::kw_u:
353  case Token::Kind::identifier:
354  case Token::Kind::kw_barrier:
355  ret.emplace_back(parse_gop());
356  break;
357 
358  default:
359  finished = true;
360  break;
361  }
362  }
363 
364  return ret;
365  }
366 
377  StatementPtr parse_qop() {
378  switch (current_token_.kind()) {
379  case Token::Kind::kw_cx:
380  case Token::Kind::kw_u:
381  case Token::Kind::identifier:
382  return StatementPtr(parse_gop());
383 
384  case Token::Kind::kw_measure:
385  return parse_measure();
386 
387  case Token::Kind::kw_reset:
388  return parse_reset();
389 
390  default:
391  error_ = true;
392  if (!supress_errors_) {
393  std::cerr << current_token_.location();
394  std::cerr << ": expected a quantum operation, but got ";
395  std::cerr << current_token_.kind() << "\n";
396  ;
397  supress_errors_ = true;
398  }
399 
400  return nullptr;
401  }
402  }
403 
417  GatePtr parse_gop() {
418  switch (current_token_.kind()) {
419  case Token::Kind::kw_u:
420  return parse_unitary();
421 
422  case Token::Kind::kw_cx:
423  return parse_cnot();
424 
425  case Token::Kind::identifier:
426  return parse_gate_statement();
427 
428  case Token::Kind::kw_barrier:
429  return parse_barrier();
430 
431  default:
432  error_ = true;
433  if (!supress_errors_) {
434  std::cerr << current_token_.location();
435  std::cerr << ": expected a gate operation but got ";
436  std::cerr << current_token_.kind() << "\n";
437  ;
438  supress_errors_ = true;
439  }
440 
441  return nullptr;
442  }
443  }
444 
454  std::vector<ident> parse_idlist() {
455  std::vector<ident> ret;
456 
457  // doesn't accept empty lists
458  while (true) {
459  auto identifier = expect_and_consume_token(Token::Kind::identifier);
460  ret.push_back(identifier);
461  if (!try_and_consume_token(Token::Kind::comma)) {
462  break;
463  }
464  }
465 
466  return ret;
467  }
468 
478  Varinfo parse_argument() {
479  auto loc = current_token_.location();
480 
481  auto id = expect_and_consume_token(Token::Kind::identifier);
482  if (try_and_consume_token(Token::Kind::l_square)) {
483  auto offset = expect_and_consume_token(Token::Kind::nninteger);
484  expect_and_consume_token(Token::Kind::r_square);
485 
486  return Varinfo(loc, id, offset);
487  }
488 
489  return Varinfo(loc, id);
490  }
491 
501  std::vector<Varinfo> parse_anylist() {
502  std::vector<Varinfo> ret;
503 
504  // doesn't accept empty lists
505  while (true) {
506  auto arg = parse_argument();
507  ret.push_back(arg);
508  if (!try_and_consume_token(Token::Kind::comma)) {
509  break;
510  }
511  }
512 
513  return ret;
514  }
515 
525  std::vector<ExprPtr> parse_explist() {
526  // doesn't accept empty lists
527  std::vector<ExprPtr> ret;
528 
529  while (true) {
530  auto exp = parse_exp();
531  ret.push_back(std::move(exp));
532  if (!try_and_consume_token(Token::Kind::comma)) {
533  break;
534  }
535  }
536 
537  return ret;
538  }
539 
554  ExprPtr parse_exp(int min_precedence = 1) {
555  auto loc = current_token_.location();
556 
557  auto lexp = parse_atom();
558  while (1) {
559  auto next_min_precedence = min_precedence;
560 
561  switch (current_token_.kind()) {
562  case Token::Kind::plus:
563  if (min_precedence > 1) {
564  return lexp;
565  }
566  next_min_precedence = 2;
567  break;
568 
569  case Token::Kind::minus:
570  if (min_precedence > 1) {
571  return lexp;
572  }
573  next_min_precedence = 2;
574  break;
575 
576  case Token::Kind::star:
577  if (min_precedence > 2) {
578  return lexp;
579  }
580  next_min_precedence = 3;
581  break;
582 
583  case Token::Kind::slash:
584  if (min_precedence > 2) {
585  return lexp;
586  }
587  next_min_precedence = 3;
588  break;
589 
590  case Token::Kind::caret:
591  if (min_precedence > 3) {
592  return lexp;
593  }
594  next_min_precedence = 4;
595  break;
596 
597  default:
598  return lexp;
599  }
600 
601  auto bop = parse_binaryop();
602  auto rexp = parse_exp(next_min_precedence);
603  lexp =
604  ExprPtr(new BExpr(loc, std::move(lexp), bop, std::move(rexp)));
605  }
606 
607  return lexp;
608  }
609 
616  ExprPtr parse_atom() {
617  auto loc = current_token_.location();
618 
619  switch (current_token_.kind()) {
620  case Token::Kind::l_paren: {
621  consume_token();
622  auto exp = parse_exp();
623  expect_and_consume_token(Token::Kind::r_paren);
624  return exp;
625  }
626 
627  case Token::Kind::minus: {
628  consume_token();
629  auto exp = parse_exp();
630  return ExprPtr(new UExpr(loc, UnaryOp::Neg, std::move(exp)));
631  }
632 
633  case Token::Kind::identifier: {
634  auto identifier = current_token_;
635  consume_token();
636  return ExprPtr(new VarExpr(loc, identifier));
637  }
638  case Token::Kind::nninteger: {
639  auto integer = current_token_;
640  consume_token();
641  return ExprPtr(new IntExpr(loc, integer));
642  }
643  case Token::Kind::kw_pi:
644  consume_token();
645  return ExprPtr(new PiExpr(loc));
646  case Token::Kind::real: {
647  auto real = current_token_;
648  consume_token();
649  return ExprPtr(new RealExpr(loc, real));
650  }
651 
652  case Token::Kind::kw_sin:
653  case Token::Kind::kw_cos:
654  case Token::Kind::kw_tan:
655  case Token::Kind::kw_exp:
656  case Token::Kind::kw_ln:
657  case Token::Kind::kw_sqrt: {
658  auto op = parse_unaryop();
659  expect_and_consume_token(Token::Kind::l_paren);
660  auto exp = parse_exp();
661  expect_and_consume_token(Token::Kind::r_paren);
662  return ExprPtr(new UExpr(loc, op, std::move(exp)));
663  }
664 
665  default:
666  error_ = true;
667  if (!supress_errors_) {
668  std::cerr << current_token_.location();
669  std::cerr << ": expected an atomic expression but got ";
670  std::cerr << current_token_.kind() << "\n";
671  ;
672  supress_errors_ = true;
673  }
674 
675  return nullptr;
676  }
677  }
678 
685  BinaryOp parse_binaryop() {
686  switch (current_token_.kind()) {
687  case Token::Kind::plus:
688  consume_token();
689  return BinaryOp::Plus;
690  case Token::Kind::minus:
691  consume_token();
692  return BinaryOp::Minus;
693  case Token::Kind::star:
694  consume_token();
695  return BinaryOp::Times;
696  case Token::Kind::slash:
697  consume_token();
698  return BinaryOp::Divide;
699  case Token::Kind::caret:
700  consume_token();
701  return BinaryOp::Pow;
702  default:
703  error_ = true;
704  if (!supress_errors_) {
705  std::cerr << current_token_.location();
706  std::cerr << ": expected a binary operator but got ";
707  std::cerr << current_token_.kind() << "\n";
708  ;
709  supress_errors_ = true;
710  }
711 
712  return BinaryOp::Plus;
713  }
714  }
715 
722  UnaryOp parse_unaryop() {
723  switch (current_token_.kind()) {
724  case Token::Kind::kw_sin:
725  consume_token();
726  return UnaryOp::Sin;
727  case Token::Kind::kw_cos:
728  consume_token();
729  return UnaryOp::Cos;
730  case Token::Kind::kw_tan:
731  consume_token();
732  return UnaryOp::Tan;
733  case Token::Kind::kw_exp:
734  consume_token();
735  return UnaryOp::Exp;
736  case Token::Kind::kw_ln:
737  consume_token();
738  return UnaryOp::Ln;
739  case Token::Kind::kw_sqrt:
740  consume_token();
741  return UnaryOp::Sqrt;
742  default:
743  error_ = true;
744  if (!supress_errors_) {
745  std::cerr << current_token_.location();
746  std::cerr << ": expected a unary operator but got ";
747  std::cerr << current_token_.kind() << "\n";
748  ;
749  supress_errors_ = true;
750  }
751 
752  return UnaryOp::Neg;
753  }
754  }
755 
763  GatePtr parse_cnot() {
764  auto loc = current_token_.location();
765 
766  expect_and_consume_token(Token::Kind::kw_cx);
767  auto ctrl = parse_argument();
768  expect_and_consume_token(Token::Kind::comma);
769  auto tgt = parse_argument();
770  consume_until(Token::Kind::semicolon);
771 
772  return GatePtr(new CNOTGate(loc, ctrl, tgt));
773  }
774 
782  GatePtr parse_unitary() {
783  auto loc = current_token_.location();
784 
785  expect_and_consume_token(Token::Kind::kw_u);
786  expect_and_consume_token(Token::Kind::l_paren);
787  auto theta = parse_exp();
788  expect_and_consume_token(Token::Kind::comma);
789  auto phi = parse_exp();
790  expect_and_consume_token(Token::Kind::comma);
791  auto lambda = parse_exp();
792  expect_and_consume_token(Token::Kind::r_paren);
793  auto arg = parse_argument();
794  consume_until(Token::Kind::semicolon);
795 
796  return GatePtr(new UGate(loc, std::move(theta), std::move(phi),
797  std::move(lambda), arg));
798  }
799 
808  GatePtr parse_gate_statement() {
809  auto loc = current_token_.location();
810 
811  auto id = expect_and_consume_token(Token::Kind::identifier);
812  std::vector<ExprPtr> c_args;
813  if (try_and_consume_token(Token::Kind::l_paren)) {
814  c_args = parse_explist();
815  expect_and_consume_token(Token::Kind::r_paren);
816  }
817 
818  auto q_args = parse_anylist();
819  consume_until(Token::Kind::semicolon);
820 
821  return GatePtr(new DeclaredGate(loc, id, std::move(c_args), q_args));
822  }
823 
831  StatementPtr parse_measure() {
832  auto loc = current_token_.location();
833 
834  expect_and_consume_token(Token::Kind::kw_measure);
835  auto q_arg = parse_argument();
836  expect_and_consume_token(Token::Kind::arrow);
837  auto c_arg = parse_argument();
838  consume_until(Token::Kind::semicolon);
839 
840  return StatementPtr(new MeasureStatement(loc, q_arg, c_arg));
841  }
842 
850  StatementPtr parse_reset() {
851  auto loc = current_token_.location();
852 
853  expect_and_consume_token(Token::Kind::kw_reset);
854  auto arg = parse_argument();
855  consume_until(Token::Kind::semicolon);
856 
857  return StatementPtr(new ResetStatement(loc, arg));
858  }
859 
867  GatePtr parse_barrier() {
868  auto loc = current_token_.location();
869 
870  expect_and_consume_token(Token::Kind::kw_barrier);
871  auto args = parse_anylist();
872  consume_until(Token::Kind::semicolon);
873 
874  return GatePtr(new BarrierGate(loc, args));
875  }
876 
884  StatementPtr parse_if() {
885  auto loc = current_token_.location();
886 
887  expect_and_consume_token(Token::Kind::kw_if);
888  expect_and_consume_token(Token::Kind::l_paren);
889  auto identifier = expect_and_consume_token(Token::Kind::identifier);
890  expect_and_consume_token(Token::Kind::equalequal);
891  auto integer = expect_and_consume_token(Token::Kind::nninteger);
892  expect_and_consume_token(Token::Kind::r_paren);
893  auto op = parse_qop();
894 
895  return StatementPtr(
896  new IfStatement(loc, identifier, integer, std::move(op)));
897  }
898 };
899 
900 } /* namespace qasm */
901 } /* namespace qpp */
902 
903 #endif /* QASM_PARSER_H_ */
qpp
Quantum++ main namespace.
Definition: circuits.h:35
Generated by   doxygen 1.8.11