46. Метаязык Хомского
Метаязык Хомского вышел из недр математической логики. Он имеет следующую систему обозначений:
- символ “®” отделяет левую часть правила от правой (читается как "порождает" и "это есть");
- нетерминалы обозначаются буквой А с индексом, указывающим на его номер;
- терминалы - это символы используемые в описываемом языке;
- каждое правило определяет порождение одной новой цепочки, причем один и тот же нетерминал может встречаться в нескольких правилах слева.
Описание идентификатора на метаязыке Хомского будет выглядеть следующим образом:
|
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 |
|
Метаязык Хомского-Щутценберже
Приведенный в предыдущем разделе пример описания идентификатора показывает громоздкость метаязыка Хомского, что позволяет эффективно использовать его только для описания небольших абстрактных языков. Более компактное описание возможно с применением метаязыка Хомского-Щутценберже, использующего следующие обозначения метасимволов:
· символ “=” отделяет левую часть правила от правой (вместо символа “®”);
- нетерминалы обозначаются буквой А с индексом, указывающим на его номер;
- терминалы - это символы используемые в описываемом языке;
- каждое правило определяет порождение нескольких альтернативных цепочек, отделяемых друг от друга символом “+”, что позволяет, при желании, использовать в левой части только разные нетерминалы.
Введение возможности альтернативного перечисления позволило сократить описание языков. Описание идентификатора будет выглядеть следующим образом:
- A1=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
- A2=0+1+2+4+5+6+7+8+9
- A3=A1+A3A1+A3A2
| 