Метаязык Хомского

Метаязык Хомского вышел из недр математической логики. Он имеет следующую систему обозначений:

• символ “” отделяет левую часть правила от правой (читается как "порождает" и "это есть");

• нетерминалы обозначаются буквой А с индексом, указывающим на его номер;

• терминалы - это символы используемые в описываемом языке;

• каждое правило определяет порождение одной новой цепочки, причем один и тот же нетерминал может встречаться в нескольких правилах слева.

Описание идентификатора на метаязыке Хомского будет выглядеть следующим образом:

1. A1  A	23. A1  W	45. A1  s
2. A1  B	24. A1  X	46. A1  t
3. A1  C	25. A1  Y	47. A1  u
4. A1  D	26. A1  Z	48. A1  v
5. A1  E	27. A1  a	49. A1  w
6. A1  F	28. A1  b	50. A1  x
7. A1  G	29. A1  c	51. A1  y
8. A1  H	30. A1  d	52. A1  z
9. A1  I	31. A1  e	53. A2  0
10. A1  J	32. A1  f	54. A2  1
11. A1  K	33. A1  g	55. A2  2
12. A1  L	34. A1  h	56. A2  3
13. A1  M	35. A1  i	57. A2  4
14. A1  N	36. A1  j	58. A2  5
15. A1  O	37. A1  k	59. A2  6
16. A1  P	38. A1  l	60. A2  7
17. A1  Q	39. A1  m	61. A2  8
18. A1  R	40. A1  n	62. A2  9
19. A1  S	41. A1  o	63. A3  A1
20. A1  T	42. A1  p	64. A3  A3A1
21. A1  U	43. A1  q	65. A3  A3A2
22. A1  V	44. A1  r

Метаязык Хомского-Щутценберже

Приведенный в предыдущем разделе пример описания идентификатора показывает громоздкость метаязыка Хомского, что позволяет эффективно использовать его только для описания небольших абстрактных языков. Более компактное описание возможно с применением метаязыка Хомского-Щутценберже, использующего следующие обозначения метасимволов:

• символ “=” отделяет левую часть правила от правой (вместо символа “”);

• нетерминалы обозначаются буквой А с индексом, указывающим на его номер;

• терминалы - это символы используемые в описываемом языке;

• каждое правило определяет порождение нескольких альтернативных цепочек, отделяемых друг от друга символом “+”, что позволяет, при желании, использовать в левой части только разные нетерминалы.

Введение возможности альтернативного перечисления позволило сократить описание языков. Описание идентификатора будет выглядеть следующим образом:

1. A₁=A+B+C+D+E+F+G+H+I+J+K+L+M+N+O+P+Q+R+S+T+ U+V+W+X+Y+Z+a+b+c+d+e+f+g+h+i+j+k+l+m+n+o+p+q+ r+s+t+u+v+w+x+y+z

2. A₂=0+1+2+4+5+6+7+8+9

3. A₃=A₁+A₃A₁+A₃A₂