From 39acf19a14b1c9287c66a097c4ac5d1d26d6f033 Mon Sep 17 00:00:00 2001 From: thurston Date: Mon, 29 Jan 2007 00:08:19 +0000 Subject: [PATCH] More content added. Did a smallish reorganization. Needs a lot of cleanup still. git-svn-id: http://svn.complang.org/ragel/trunk@28 052ea7fc-9027-0410-9066-f65837a77df0 --- doc/conds1.fig | 80 ++ doc/conds2.fig | 86 ++ doc/dropdown.fig | 107 ++ doc/ragel-guide.tex | 3066 +++++++++++++++++++++++++++++---------------------- 4 files changed, 1996 insertions(+), 1343 deletions(-) create mode 100644 doc/conds1.fig create mode 100644 doc/conds2.fig create mode 100644 doc/dropdown.fig diff --git a/doc/conds1.fig b/doc/conds1.fig new file mode 100644 index 0000000..24e82bf --- /dev/null +++ b/doc/conds1.fig @@ -0,0 +1,80 @@ +#FIG 3.2 +Portrait +Center +Metric +A4 +100.00 +Single +-2 +# Generated by dot version 2.2.1 (Fri Sep 30 13:22:44 UTC 2005) +# For: (age) Adrian Thurston +# Title: conds1 +# Pages: 1 +1200 2 +0 32 #d2d2d2 +# ENTRY +1 1 0 1 0 0 0 0 20 0.000 0 0.0000 33 4650 33 33 33 4650 66 4683 +# 0 +1 1 0 1 0 32 0 0 -1 0.000 0 0.0000 1400 4650 383 383 1400 4650 1783 5033 +1 1 0 1 0 32 0 0 -1 0.000 0 0.0000 1400 4650 450 450 1400 4650 1850 5100 +4 1 0 0 0 0 14.0 0.0000 2 0.0 0.0 1400 4733 0\001 +# ENTRY -> 0 +3 4 0 1 0 0 0 0 -1 0.0 0 0 0 7 + 66 4650 132 4650 225 4650 341 4650 474 4650 617 4650 766 4650 + 0 1 1 1 1 1 0 +2 3 0 1 0 0 0 0 20 0.0 0 0 0 0 0 4 + 766 4583 933 4650 766 4700 766 4583 +4 1 0 0 0 0 14.0 0.0000 2 0.0 0.0 500 4600 IN\001 +# 1 +1 1 0 1 0 0 0 0 -1 0.000 0 0.0000 3233 4650 383 383 3233 4650 3616 5033 +4 1 0 0 0 0 14.0 0.0000 2 0.0 0.0 3233 4733 1\001 +# 0 -> 1 +3 4 0 1 0 0 0 0 -1 0.0 0 0 0 7 + 1866 4650 1995 4650 2129 4650 2266 4650 2403 4650 2537 4650 2666 4650 + 0 1 1 1 1 1 0 +2 3 0 1 0 0 0 0 20 0.0 0 0 0 0 0 4 + 2666 4583 2833 4650 2666 4700 2666 4583 +4 1 0 0 0 0 14.0 0.0000 2 0.0 0.0 2350 4600 100\001 +# 3 +1 1 0 1 0 0 0 0 -1 0.000 0 0.0000 8466 4650 383 383 8466 4650 8849 5033 +1 1 0 1 0 0 0 0 -1 0.000 0 0.0000 8466 4650 450 450 8466 4650 8916 5100 +4 1 0 0 0 0 14.0 0.0000 2 0.0 0.0 8466 4733 3\001 +# 3 -> 3 +3 4 0 1 0 0 0 0 -1 0.0 0 0 0 13 + 8783 4316 8808 4210 8801 4112 8762 4027 8693 3959 8594 3915 8466 3900 8372 3908 8291 3931 8225 3968 8175 4018 8144 4079 8133 4150 + 0 1 1 1 1 1 1 1 1 1 1 1 0 +2 3 0 1 0 0 0 0 20 0.0 0 0 0 0 0 4 + 8183 4150 8150 4316 8083 4150 8183 4150 +4 1 0 0 0 0 14.0 0.0000 2 0.0 0.0 8466 3850 97..122(test_len)\001 +# 3 -> 1 +3 4 0 1 0 0 0 0 -1 0.0 0 0 0 19 + 8016 4633 7959 4632 7904 4629 7852 4625 7800 4620 7750 4617 7700 4616 7136 4601 6679 4589 6272 4581 5865 4577 5403 4577 4833 4583 4661 4591 4483 4600 4302 4608 4122 4616 3947 4625 3783 4633 + 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 +2 3 0 1 0 0 0 0 20 0.0 0 0 0 0 0 4 + 3783 4683 3616 4633 3783 4566 3783 4683 +4 1 0 0 0 0 14.0 0.0000 2 0.0 0.0 5500 4533 100(!test_len)\001 +# 2 +1 1 0 1 0 0 0 0 -1 0.000 0 0.0000 5500 5683 383 383 5500 5683 5883 6066 +4 1 0 0 0 0 14.0 0.0000 2 0.0 0.0 5500 5766 2\001 +# 1 -> 2 +3 4 0 1 0 0 0 0 -1 0.0 0 0 0 7 + 3600 4816 3800 4908 4029 5014 4275 5127 4525 5241 4771 5351 5000 5450 + 0 1 1 1 1 1 0 +2 3 0 1 0 0 0 0 20 0.0 0 0 0 0 0 4 + 5016 5400 5150 5516 4966 5500 5016 5400 +4 1 0 0 0 0 14.0 0.0000 2 0.0 0.0 4233 4966 48..57\001 +# 2 -> 3 +3 4 0 1 0 0 0 0 -1 0.0 0 0 0 7 + 5866 5550 6147 5455 6477 5342 6835 5218 7200 5090 7550 4965 7866 4850 + 0 1 1 1 1 1 0 +2 3 0 1 0 0 0 0 20 0.0 0 0 0 0 0 4 + 7850 4800 8033 4800 7883 4900 7850 4800 +4 1 0 0 0 0 14.0 0.0000 2 0.0 0.0 7083 4900 58 / rec_num\001 +# 2 -> 2 +3 4 0 1 0 0 0 0 -1 0.0 0 0 0 13 + 5766 5400 5787 5300 5782 5207 5752 5125 5695 5059 5611 5015 5500 5000 5416 5008 5348 5030 5295 5066 5256 5113 5230 5169 5216 5233 + 0 1 1 1 1 1 1 1 1 1 1 1 0 +2 3 0 1 0 0 0 0 20 0.0 0 0 0 0 0 4 + 5266 5233 5233 5400 5166 5233 5266 5233 +4 1 0 0 0 0 14.0 0.0000 2 0.0 0.0 5500 4950 48..57\001 +# end of FIG file diff --git a/doc/conds2.fig b/doc/conds2.fig new file mode 100644 index 0000000..d1cf959 --- /dev/null +++ b/doc/conds2.fig @@ -0,0 +1,86 @@ +#FIG 3.2 +Portrait +Center +Metric +A4 +100.00 +Single +-2 +# Generated by dot version 2.2.1 (Fri Sep 30 13:22:44 UTC 2005) +# For: (age) Adrian Thurston +# Title: conds2 +# Pages: 1 +1200 2 +0 32 #d2d2d2 +# ENTRY +1 1 0 1 0 0 0 0 20 0.000 0 0.0000 33 4350 33 33 33 4350 66 4383 +# 0 +1 1 0 1 0 32 0 0 -1 0.000 0 0.0000 1333 4350 383 383 1333 4350 1716 4733 +4 1 0 0 0 0 14.0 0.0000 2 0.0 0.0 1333 4433 0\001 +# ENTRY -> 0 +3 4 0 1 0 0 0 0 -1 0.0 0 0 0 7 + 66 4350 139 4350 237 4350 354 4350 485 4350 624 4350 766 4350 + 0 1 1 1 1 1 0 +2 3 0 1 0 0 0 0 20 0.0 0 0 0 0 0 4 + 766 4283 933 4350 766 4400 766 4283 +4 1 0 0 0 0 14.0 0.0000 2 0.0 0.0 500 4300 IN\001 +# 2 +1 1 0 1 0 0 0 0 -1 0.000 0 0.0000 11633 5016 383 383 11633 5016 12016 5399 +1 1 0 1 0 0 0 0 -1 0.000 0 0.0000 11633 5016 450 450 11633 5016 12083 5466 +4 1 0 0 0 0 14.0 0.0000 2 0.0 0.0 11633 5100 2\001 +# 1 +1 1 0 1 0 0 0 0 -1 0.000 0 0.0000 9183 4433 383 383 9183 4433 9566 4816 +4 1 0 0 0 0 14.0 0.0000 2 0.0 0.0 9183 4516 1\001 +# 0 -> 1 +3 4 0 1 0 0 0 0 -1 0.0 0 0 0 25 + 1716 4283 1773 4282 1828 4278 1881 4272 1932 4266 1983 4258 2033 4250 2352 4232 2611 4227 2839 4231 3066 4238 3321 4246 3633 4250 4551 4259 5297 4260 5956 4260 6613 4267 7355 4288 8266 4333 8325 4340 8383 4345 8441 4350 8499 4354 8558 4359 8616 4366 + 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 +2 3 0 1 0 0 0 0 20 0.0 0 0 0 0 0 4 + 8616 4316 8783 4383 8616 4416 8616 4316 +4 1 0 0 0 0 14.0 0.0000 2 0.0 0.0 4766 4216 97..122(!test_len)\001 +# 3 +1 1 0 1 0 0 0 0 -1 0.000 0 0.0000 4766 5383 383 383 4766 5383 5149 5766 +4 1 0 0 0 0 14.0 0.0000 2 0.0 0.0 4766 5466 3\001 +# 0 -> 3 +3 4 0 1 0 0 0 0 -1 0.0 0 0 0 7 + 1716 4466 2062 4570 2479 4694 2935 4829 3398 4966 3835 5098 4216 5216 + 0 1 1 1 1 1 0 +2 3 0 1 0 0 0 0 20 0.0 0 0 0 0 0 4 + 4233 5166 4383 5266 4200 5266 4233 5166 +4 1 0 0 0 0 14.0 0.0000 2 0.0 0.0 2833 4533 97..122(test_len)\001 +# 1 -> 2 +3 4 0 1 0 0 0 0 -1 0.0 0 0 0 7 + 9566 4516 9774 4564 10009 4622 10260 4685 10518 4750 10773 4811 11016 4866 + 0 1 1 1 1 1 0 +2 3 0 1 0 0 0 0 20 0.0 0 0 0 0 0 4 + 11033 4816 11183 4916 11000 4916 11033 4816 +4 1 0 0 0 0 14.0 0.0000 2 0.0 0.0 10483 4633 10 / two\001 +# 1 -> 1 +3 4 0 1 0 0 0 0 -1 0.0 0 0 0 13 + 9450 4150 9470 4050 9466 3957 9435 3875 9378 3809 9294 3765 9183 3750 9099 3758 9032 3780 8979 3816 8940 3863 8914 3919 8900 3983 + 0 1 1 1 1 1 1 1 1 1 1 1 0 +2 3 0 1 0 0 0 0 20 0.0 0 0 0 0 0 4 + 8950 3983 8916 4150 8850 3983 8950 3983 +4 1 0 0 0 0 14.0 0.0000 2 0.0 0.0 9183 3700 48..57, 97..122\001 +# 3 -> 2 +3 4 0 1 0 0 0 0 -1 0.0 0 0 0 13 + 5166 5383 5685 5380 6364 5370 7158 5352 8024 5324 8919 5284 9800 5233 10010 5215 10222 5195 10433 5172 10638 5149 10833 5124 11016 5100 + 0 1 1 1 1 1 1 1 1 1 1 1 0 +2 3 0 1 0 0 0 0 20 0.0 0 0 0 0 0 4 + 11016 5050 11183 5083 11016 5150 11016 5050 +4 1 0 0 0 0 14.0 0.0000 2 0.0 0.0 9183 5183 10 / one, two\001 +# 3 -> 1 +3 4 0 1 0 0 0 0 -1 0.0 0 0 0 7 + 5150 5300 5623 5200 6208 5075 6854 4937 7508 4796 8118 4663 8633 4550 + 0 1 1 1 1 1 0 +2 3 0 1 0 0 0 0 20 0.0 0 0 0 0 0 4 + 8633 4500 8800 4516 8650 4600 8633 4500 +4 1 0 0 0 0 14.0 0.0000 2 0.0 0.0 7083 4616 48..57, 97..122(!test_len)\001 +# 3 -> 3 +3 4 0 1 0 0 0 0 -1 0.0 0 0 0 13 + 5033 5100 5054 5000 5049 4907 5018 4825 4961 4759 4877 4715 4766 4700 4683 4708 4615 4730 4562 4766 4523 4813 4497 4869 4483 4933 + 0 1 1 1 1 1 1 1 1 1 1 1 0 +2 3 0 1 0 0 0 0 20 0.0 0 0 0 0 0 4 + 4533 4933 4500 5100 4433 4933 4533 4933 +4 1 0 0 0 0 14.0 0.0000 2 0.0 0.0 4766 4650 97..122(test_len)\001 +# end of FIG file diff --git a/doc/dropdown.fig b/doc/dropdown.fig new file mode 100644 index 0000000..29fefec --- /dev/null +++ b/doc/dropdown.fig @@ -0,0 +1,107 @@ +#FIG 3.2 Produced by xfig version 3.2.5-alpha5 +Portrait +Center +Metric +A4 +100.00 +Single +-2 +# Generated by dot version 2.2.1 (Fri Sep 30 13:22:44 UTC 2005) +# For: (age) Adrian Thurston +# Title: dropdown +# Pages: 1 +1200 2 +0 32 #d2d2d2 +# ENTRY +1 1 0 1 0 0 0 0 20 0.000 0 0.0000 33 3950 33 33 33 3950 66 3983 +# 0 +1 1 0 1 0 32 0 0 -1 0.000 0 0.0000 1333 3950 383 383 1333 3950 1716 4333 +# 3 +1 1 0 1 0 0 0 0 -1 0.000 0 0.0000 9266 4133 383 383 9266 4133 9649 4516 +1 1 0 1 0 0 0 0 -1 0.000 0 0.0000 9266 4133 450 450 9266 4133 9716 4583 +# 1 +1 1 0 1 0 0 0 0 -1 0.000 0 0.0000 5383 3550 383 383 5383 3550 5766 3933 +# 2 +1 1 0 1 0 0 0 0 -1 0.000 0 0.0000 7566 4133 383 383 7566 4133 7949 4516 +2 3 0 1 0 0 0 0 20 0.000 0 0 0 0 0 4 + 766 3883 933 3950 766 4000 766 3883 +2 3 0 1 0 0 0 0 20 0.000 0 0 0 0 0 4 + 1100 3500 1066 3666 1000 3500 1100 3500 +2 3 0 1 0 0 0 0 20 0.000 0 0 0 0 0 4 + 4816 3433 4983 3500 4816 3533 4816 3433 +2 3 0 1 0 0 0 0 20 0.000 0 0 0 0 0 4 + 1883 4066 1716 4000 1883 3966 1883 4066 +2 3 0 1 0 0 0 0 20 0.000 0 0 0 0 0 4 + 7033 3933 7183 4033 7000 4033 7033 3933 +2 3 0 1 0 0 0 0 20 0.000 0 0 0 0 0 4 + 8633 4066 8800 4133 8633 4183 8633 4066 +2 3 0 1 0 0 0 0 20 0.000 0 0 0 0 0 4 + 1833 4216 1666 4150 1833 4116 1833 4216 +2 3 0 1 0 0 0 0 20 0.000 0 0 0 0 0 4 + 7333 3683 7300 3850 7233 3683 7333 3683 +2 2 0 0 0 7 50 -1 -1 0.000 0 0 -1 0 0 5 + -90 2970 9765 2970 9765 4680 -90 4680 -90 2970 +# ENTRY -> 0 +3 4 0 1 0 0 0 0 -1 0.000 0 0 0 7 + 66 3950 139 3950 237 3950 354 3950 485 3950 624 3950 + 766 3950 + 0.000 1.000 1.000 1.000 1.000 1.000 0.000 +# 0 -> 0 +3 4 0 1 0 0 0 0 -1 0.000 0 0 0 13 + 1600 3666 1620 3567 1616 3474 1585 3391 1528 3325 1444 3282 + 1333 3266 1249 3274 1182 3297 1129 3333 1090 3380 1064 3436 + 1050 3500 + 0.000 1.000 1.000 1.000 1.000 1.000 1.000 1.000 + 1.000 1.000 1.000 1.000 0.000 +# 0 -> 1 +3 4 0 1 0 0 0 0 -1 0.000 0 0 0 13 + 1666 3750 1726 3725 1787 3700 1850 3677 1912 3654 1973 3634 + 2033 3616 2528 3528 3036 3474 3537 3450 4013 3447 4446 3460 + 4816 3483 + 0.000 1.000 1.000 1.000 1.000 1.000 1.000 1.000 + 1.000 1.000 1.000 1.000 0.000 +# 1 -> 0 +3 4 0 1 0 0 0 0 -1 0.000 0 0 0 13 + 5033 3716 4892 3768 4738 3823 4575 3877 4406 3926 4235 3968 + 4066 4000 3689 4046 3300 4070 2912 4077 2538 4067 2190 4046 + 1883 4016 + 0.000 1.000 1.000 1.000 1.000 1.000 1.000 1.000 + 1.000 1.000 1.000 1.000 0.000 +# 1 -> 2 +3 4 0 1 0 0 0 0 -1 0.000 0 0 0 7 + 5766 3650 5954 3695 6161 3747 6379 3804 6600 3863 6815 3923 + 7016 3983 + 0.000 1.000 1.000 1.000 1.000 1.000 0.000 +# 2 -> 3 +3 4 0 1 0 0 0 0 -1 0.000 0 0 0 7 + 7966 4133 8069 4133 8176 4133 8287 4133 8401 4133 8516 4133 + 8633 4133 + 0.000 1.000 1.000 1.000 1.000 1.000 0.000 +# 2 -> 0 +3 4 0 1 0 0 0 0 -1 0.000 0 0 0 19 + 7183 4233 7062 4258 6935 4282 6804 4304 6669 4323 6534 4339 + 6400 4350 5539 4415 4838 4443 4216 4433 3595 4384 2893 4295 + 2033 4166 1999 4166 1966 4166 1933 4166 1899 4166 1866 4166 + 1833 4166 + 0.000 1.000 1.000 1.000 1.000 1.000 1.000 1.000 + 1.000 1.000 1.000 1.000 1.000 1.000 1.000 1.000 + 1.000 1.000 0.000 +# 2 -> 2 +3 4 0 1 0 0 0 0 -1 0.000 0 0 0 13 + 7833 3850 7854 3750 7849 3657 7818 3575 7761 3509 7677 3465 + 7566 3450 7483 3458 7415 3480 7362 3516 7323 3563 7297 3619 + 7283 3683 + 0.000 1.000 1.000 1.000 1.000 1.000 1.000 1.000 + 1.000 1.000 1.000 1.000 0.000 +4 1 0 0 0 0 14 0.0000 2 150 120 1333 4033 0\001 +4 1 0 0 0 0 14 0.0000 2 150 255 500 3900 IN\001 +4 1 0 0 0 0 14 0.0000 2 150 120 9266 4216 3\001 +4 1 0 0 0 0 14 0.0000 2 150 1170 1333 3216 DEF / bchar\001 +4 1 0 0 0 0 14 0.0000 2 165 120 5383 3633 1\001 +4 1 0 0 0 0 14 0.0000 2 195 165 3050 3416 ']'\001 +4 1 0 0 0 0 14 0.0000 2 195 2055 3050 3950 DEF / bbrack1, bchar\001 +4 1 0 0 0 0 14 0.0000 2 150 120 7566 4216 2\001 +4 1 0 0 0 0 14 0.0000 2 195 165 6783 3883 ']'\001 +4 1 0 0 0 0 14 0.0000 2 150 225 8383 4083 '>'\001 +4 1 0 0 0 0 14 0.0000 2 195 2055 5383 4300 DEF / bbrack2, bchar\001 +4 1 0 0 0 0 14 0.0000 2 210 1110 7566 3400 ']' / bbrack1\001 diff --git a/doc/ragel-guide.tex b/doc/ragel-guide.tex index 7573e25..28e80f1 100644 --- a/doc/ragel-guide.tex +++ b/doc/ragel-guide.tex @@ -568,20 +568,6 @@ set of states. At a very minimum the \verb|main| machine must be instantiated. Other machines may be instantiated and control passed to them by use of \verb|fcall|, \verb|fgoto| or \verb|fnext| statements. -\begin{comment} -\subsection{Write Statement} - -\begin{verbatim} -write [options]; -\end{verbatim} -\verbspace - -The write statement is used to generate parts of the machine. There are four -components that can be generated: the state machine's static data, the -initialization code, the execution code and the EOF action execution code. The -write statement is described in detail in Section \ref{write-statement}. -\end{comment} - \section{Lexical Analysis of an FSM Specification} \label{lexing} @@ -1330,1678 +1316,2072 @@ Character-level negation produces a machine that matches any single character not matched by the given machine. Character-Level Negation is equivalent to \verb|(any - expr)|. -\section{State Charts} +\section{State Machine Minimization} -It is not uncommon for programmers to implement -parsers as manually-coded state machines, either using a switch statement or a -state map compiler which takes a list of states, transitions and actions, and -generates code. - -This method can be a very effective programming technique for producing robust -code. The key disadvantage becomes clear when one attempts to comprehend such a -parser. Machines coded in this way usually require many lines, causing logic to -be spread out over large distances in the source file. Remembering the function -of a large number of states can be difficult and organizing the parser in a -sensible way requires discipline because branches and repetition present many -file layout options. This kind of programming takes a specification with -inherent structure such as looping, alternation and concatenation and expresses -it in a flat form. +State machine minimization is the process of finding the minimal equivalent FSM accepting +the language. Minimization reduces the number of states in machines +by merging equivalent states. It does not change the behaviour of the machine +in any way. It will cause some states to be merged into one because they are +functionally equivalent. State minimization is on by default. It can be turned +off with the \verb|-n| option. -If we could take an isolated component of a manually programmed state chart, -that is, a subset of states that has only one entry point, and implement it -using regular language operators then we could eliminate all the explicit -naming of the states contained in it. By eliminating explicitly named states -and replacing them with higher-level specifications we simplify a parser -specification. +The algorithm implemented is similar to Hopcroft's state minimization +algorithm. Hopcroft's algorithm assumes a finite alphabet that can be listed in +memory, whereas Ragel supports arbitrary integer alphabets that cannot be +listed in memory. Though exact analysis is very difficult, Ragel minimization +runs close to $O(n \times log(n))$ and requires $O(n)$ temporary storage where +$n$ is the number of states. -For example, sometimes chains of states are needed, with only a small number of -possible characters appearing along the chain. These can easily be replaced -with a concatenation of characters. Sometimes a group of common states -implement a loop back to another single portion of the machine. Rather than -manually duplicate all the transitions that loop back, we may be able to -express the loop using a kleene star operator. +\section{Visualization} -Ragel allows one to take this state map simplification approach. We can build -state machines using a state map model and implement portions of the state map -using regular languages. In place of any transition in the state machine, -entire sub-state machines can be given. These can encapsulate functionality -defined elsewhere. An important aspect of the Ragel approach is that when we -wrap up a collection of states using a regular expression we do not loose -access to the states and transitions. We can still execute code on the -transitions that we have encapsulated. +Ragel is able to emit compiled state machines in Graphviz's Dot file format. +Graphviz support allows users to perform +incremental visualization of their parsers. User actions are displayed on +transition labels of the graph. If the final graph is too large to be +meaningful, or even drawn, the user is able to inspect portions of the parser +by naming particular regular expression definitions with the \verb|-S| and +\verb|-M| options to the \verb|ragel| program. Use of Graphviz greatly +improves the Ragel programming experience. It allows users to learn Ragel by +experimentation and also to track down bugs caused by unintended +nondeterminism. -\subsection{Join} +\chapter{User Actions} -\verb|expr , expr , ...| -\verbspace +Ragel permits the user to embed actions into the transitions of a regular +expression's corresponding state machine. These actions are executed when the +generated code moves over a transition. Like the regular expression operators, +the action embedding operators are fully compositional. They take a state +machine and an action as input, embed the action, and yield a new state machine +which can be used in the construction of other machines. Due to the +compositional nature of embeddings, the user has complete freedom in the +placement of actions. -Join a list of machines together without -drawing any transitions, without setting up a start state, and without -designating any final states. Transitions between the machines may be specified -using labels and epsilon transitions. The start state must be explicity -specified with the ``start'' label. Final states may be specified with the an -epsilon transition to the implicitly created ``final'' state. The join -operation allows one to build machines using a state chart model. +A machine's transitions are categorized into four classes, The action embedding +operators access the transitions defined by these classes. The {\em entering +transition} operator \verb|>| isolates the start state, then embeds an action +into all transitions leaving it. The {\em finishing transition} operator +\verb|@| embeds an action into all transitions going into a final state. The +{\em all transition} operator \verb|$| embeds an action into all transitions of +an expression. The {\em pending out transition} operator \verb|%| provides +access to yet-unmade leaving transitions. -\subsection{Label} +\section{Embedding Actions} -\verb|label: expr| +\begin{verbatim} +action ActionName { + /* Code an action here. */ + count += 1; +} +\end{verbatim} \verbspace -Attaches a label to an expression. Labels can be -used as the target of epsilon transitions and explicit control transfer -statements such \verb|fgoto| and \verb|fnext| in action -code. +The action statement defines a block of code that can be embedded into an FSM. +Action names can be referenced by the action embedding operators in +expressions. Though actions need not be named in this way (literal blocks +of code can be embedded directly when building machines), defining reusable +blocks of code whenever possible is good practice because it potentially increases the +degree to which the machine can be minimized. Within an action some Ragel expressions +and statements are parsed and translated. These allow the user to interact with the machine +from action code. See Section \ref{vals} for a complete list of statements and +values available in code blocks. -\subsection{Epsilon} +\subsection{Entering Action} -\verb|expr -> label| +\verb|expr > action| \verbspace -Draws an epsilon transition to the state defined -by \verb|label|. Epsilon transitions are made deterministic when join -operators are evaluated. Epsilon transitions that are not in a join operation -are made deterministic when the machine definition that contains the epsilon is -complete. See Section \ref{labels} for information on referencing labels. +The entering operator embeds an action into the starting transitions. The +action is executed on all transitions that enter into the machine from the +start state. If the start state is a final state then it is possible for the +machine to never be entered and the starting transitions bypassed. In the +following example, the action is executed on the first transition of the +machine. If the repetition machine is bypassed the action is not executed. +\verbspace -\section{Scanners} -\label{generating-scanners} +% GENERATE: exstact +% OPT: -p +% %%{ +% machine exstact; +\begin{inline_code} +\begin{verbatim} +# Execute A at the beginning of a string of alpha. +action A {} +main := ( lower* >A ) . ' '; +\end{verbatim} +\end{inline_code} +% }%% +% END GENERATE -The longest-match operator can be used to construct scanners. The generated -machine repeatedly attempts to match one of the given patterns, first favouring -longer pattern matches over shorter ones. If there is a choice between equal -length matches, the match of the pattern which appears first is chosen. +\graphspace +\begin{center} +\includegraphics[scale=0.45]{exstact} +\end{center} +\graphspace +\subsection{Finishing Action} + +\verb|expr @ action| \verbspace + +The finishing action operator embeds an action into any transitions that go into a +final state. Whether or not the machine accepts is not determined at the point +the action is executed. Further input may move the machine out of the accepting +state, but keep it in the machine. As in the following example, the +into-final-state operator is most often used when no lookahead is necessary. + +% GENERATE: exdoneact +% OPT: -p +% %%{ +% machine exdoneact; +% action A {} +\begin{inline_code} \begin{verbatim} - := |* - pattern1 => action1; - pattern2 => action2; - ... - *|; +# Execute A when the trailing space is seen. +main := ( lower* ' ' ) @A; \end{verbatim} -\verbspace +\end{inline_code} +% }%% +% END GENERATE -The longest-match construction operator is not a pure state machine operator. -It relies on the \verb|tokstart|, \verb|tokend| and \verb|act| variables to be -present so that it can backtrack and make pointers to the matched text -available to the user. If input is processed using multiple calls to the -execute code then the user must ensure that when a token is only partially -matched that the prefix is preserved on the subsequent invocation of the -execute code. +\graphspace +\begin{center} +\includegraphics[scale=0.45]{exdoneact} +\end{center} +\graphspace -The \verb|tokstart| variable must be defined as a pointer to the input data. -It is used for recording where the current token match begins. This variable -may be used in action code for retrieving the text of the current match. Ragel -ensures that in between tokens and outside of the longest-match machines that -this pointer is set to null. In between calls to the execute code the user must -check if \verb|tokstart| is set and if so, ensure that the data it points to is -preserved ahead of the next buffer block. This is described in more detail -below. -The \verb|tokend| variable must also be defined as a pointer to the input data. -It is used for recording where a match ends and where scanning of the next -token should begin. This can also be used in action code for retrieving the -text of the current match. +\subsection{All Transition Action} -The \verb|act| variable must be defined as an integer type. It is used for -recording the identity of the last pattern matched when the scanner must go -past a matched pattern in an attempt to make a longer match. If the longer -match fails it may need to consult the act variable. In some cases use of the act -variable can be avoided because the value of the current state is enough -information to determine which token to accept, however in other cases this is -not enough and so the \verb|act| variable is used. +\verb|expr $ action| +\verbspace -When the longest-match operator is in use, the user's driver code must take on -some buffer management functions. The following algorithm gives an overview of -the steps that should be taken to properly use the longest-match operator. +The all transition operator embeds an action into all transitions of a machine. +The action is executed whenever a transition of the machine is taken. In the +following example, A is executed on every character matched. -\begin{itemize} -\setlength{\parskip}{0pt} -\item Read a block of input data. -\item Run the execute code. -\item If \verb|tokstart| is set, the execute code will expect the incomplete -token to be preserved ahead of the buffer on the next invocation of the execute -code. -\begin{itemize} -\item Shift the data beginning at \verb|tokstart| and ending at \verb|pe| to the -beginning of the input buffer. -\item Reset \verb|tokstart| to the beginning of the buffer. -\item Shift \verb|tokend| by the distance from the old value of \verb|tokstart| -to the new value. The \verb|tokend| variable may or may not be valid. There is -no way to know if it holds a meaningful value because it is not kept at null -when it is not in use. It can be shifted regardless. -\end{itemize} -\item Read another block of data into the buffer, immediately following any -preserved data. -\item Run the scanner on the new data. -\end{itemize} +% GENERATE: exallact +% OPT: -p +% %%{ +% machine exallact; +% action A {} +\begin{inline_code} +\begin{verbatim} +# Execute A on any characters of machine one or two. +main := ( 'm1' | 'm2' ) $A; +\end{verbatim} +\end{inline_code} +% }%% +% END GENERATE -Figure \ref{preserve_example} shows the required handling of an input stream in -which a token is broken by the input block boundaries. After processing up to -and including the ``t'' of ``characters'', the prefix of the string token must be -retained and processing should resume at the ``e'' on the next iteration of -the execute code. +\graphspace +\begin{center} +\includegraphics[scale=0.45]{exallact} +\end{center} +\graphspace -If one uses a large input buffer for collecting input then the number of times -the shifting must be done will be small. Furthermore, if one takes care not to -define tokens that are allowed to be very long and instead processes these -items using pure state machines or sub-scanners, then only a small amount of -data will ever need to be shifted. -\begin{figure} -\begin{verbatim} - a) A stream "of characters" to be scanned. - | | | - p tokstart pe +\subsection{Pending Out (Leaving) Actions} +\label{out-actions} - b) "of characters" to be scanned. - | | | - tokstart p pe +\verb|expr % action| +\verbspace + +The pending out action operator embeds an action into the pending out +transitions of a machine. The action is first embedded into the final states of +the machine and later transferred to any transitions made going out of the +machine. The transfer can be caused either by a concatenation or kleene star +operation. This mechanism allows one to associate an action with the +termination of a sequence, without being concerned about what particular +character terminates the sequence. In the following example, A is executed +when leaving the alpha machine by the newline character. + +% GENERATE: exoutact1 +% OPT: -p +% %%{ +% machine exoutact1; +% action A {} +\begin{inline_code} +\begin{verbatim} +# Match a word followed by an newline. Execute A when +# finishing the word. +main := ( lower+ %A ) . '\n'; \end{verbatim} -\caption{Following an invocation of the execute code there may be a partially -matched token (a). The data of the partially matched token -must be preserved ahead of the new data on the next invocation (b).} -\label{preserve_example} -\end{figure} +\end{inline_code} +% }%% +% END GENERATE -Since scanners attempt to make the longest possible match of input, in some -cases they are not able to identify a token upon parsing its final character, -they must wait for a lookahead character. For example if trying to match words, -the token match must be triggered on following whitespace in case more -characters of the word have yet to come. The user must therefore arrange for an -EOF character to be sent to the scanner to flush out any token that has not yet -been matched. The user can exclude a single character from the entire scanner -and use this character as the EOF character, possibly specifying an EOF action. -For most scanners, zero is a suitable choice for the EOF character. +\graphspace +\begin{center} +\includegraphics[scale=0.45]{exoutact1} +\end{center} +\graphspace -Alternatively, if whitespace is not significant and ignored by the scanner, the -final real token can be flushed out by simply sending an additional whitespace -character on the end of the stream. If the real stream ends with whitespace -then it will simply be extended and ignored. If it does not, then the last real token is -guaranteed to be flushed and the dummy EOF whitespace ignored. -An example scanner processing loop is given in Figure \ref{scanner-loop}. +In the following example, the \verb|term_word| action could be used to register +the appearance of a word and to clear the buffer that the \verb|lower| action used +to store the text of it. -\begin{figure} -\small +% GENERATE: exoutact2 +% OPT: -p +% %%{ +% machine exoutact2; +% action lower {} +% action space {} +% action term_word {} +% action newline {} +\begin{inline_code} \begin{verbatim} - int have = 0; - bool done = false; - while ( !done ) { - /* How much space is in the buffer? */ - int space = BUFSIZE - have; - if ( space == 0 ) { - /* Buffer is full. */ - cerr << "TOKEN TOO BIG" << endl; - exit(1); - } - - /* Read in a block after any data we already have. */ - char *p = inbuf + have; - cin.read( p, space ); - int len = cin.gcount(); +word = ( [a-z] @lower )+ %term_word; +main := word ( ' ' @space word )* '\n' @newline; +\end{verbatim} +\end{inline_code} +% }%% +% END GENERATE - /* If no data was read, send the EOF character. - if ( len == 0 ) { - p[0] = 0, len++; - done = true; - } +\graphspace +\begin{center} +\includegraphics[scale=0.45]{exoutact2} +\end{center} +\graphspace - char *pe = p + len; - %% write exec; - if ( cs == RagelScan_error ) { - /* Machine failed before finding a token. */ - cerr << "PARSE ERROR" << endl; - exit(1); - } +In this final example of the action embedding operators, A is executed upon +entering the alpha machine, B is executed on all transitions of the alpha +machine, C is executed when the alpha machine accepts by moving into the +newline machine and N is executed when the newline machine moves into a final +state. - if ( tokstart == 0 ) - have = 0; - else { - /* There is a prefix to preserve, shift it over. */ - have = pe - tokstart; - memmove( inbuf, tokstart, have ); - tokend = inbuf + (tokend-tokstart); - tokstart = inbuf; - } - } +% GENERATE: exaction +% OPT: -p +% %%{ +% machine exaction; +% action A {} +% action B {} +% action C {} +% action N {} +\begin{inline_code} +\begin{verbatim} +# Execute A on starting the alpha machine, B on every transition +# moving through it and C upon finishing. Execute N on the newline. +main := ( lower* >A $B %C ) . '\n' @N; \end{verbatim} -\caption{A processing loop for a scanner.} -\label{scanner-loop} -\end{figure} +\end{inline_code} +% }%% +% END GENERATE +\graphspace +\begin{center} +\includegraphics[scale=0.45]{exaction} +\end{center} +\graphspace -\section{Write Statement} -\label{write-statement} -\begin{verbatim} -write [options]; -\end{verbatim} -\verbspace +\section{State Action Embedding Operators} +The state embedding operators allow one to embed actions into states. Like the +transition embedding operators, there are several different classes of states +that the operators access. The meanings of the symbols are partially related to +the meanings of the symbols used by the transition embedding operators. -The write statement is used to generate parts of the machine. -There are four -components that can be generated by a write statement. These components are the -state machine's data, initialization code, execution code and EOF action -execution code. A write statement may appear before a machine is fully defined. -This allows one to write out the data first then later define the machine where -it is used. An example of this is show in Figure \ref{fbreak-example}. +The state embedding operators are different from the transition embedding +operators in that there are various kinds of events that embedded actions can +be associated with, requiring them to be distinguished by these different types +of events. The state embedding operators have two components. The first, which +is the first one or two characters, specifies the class of states that the +action will be embedded into. The second component specifies the type of event +the action will be executed on. -\subsection{Write Data} -\begin{verbatim} -write data [options]; -\end{verbatim} -\verbspace +\def\fakeitem{\hspace*{12pt}$\bullet$\hspace*{10pt}} -The write data statement causes Ragel to emit the constant static data needed -by the machine. In table-driven output styles (see Section \ref{genout}) this -is a collection of arrays that represent the states and transitions of the -machine. In goto-driven machines much less data is emitted. At the very -minimum a start state \verb|name_start| is generated. All variables written -out in machine data have both the \verb|static| and \verb|const| properties and -are prefixed with the name of the machine and an -underscore. The data can be placed inside a class, inside a function, or it can -be defined as global data. +\begin{minipage}{\textwidth} +\begin{multicols}{2} +\raggedcolumns +\noindent The different classes of states are:\\ +\fakeitem \verb|> | -- the start state \\ +\fakeitem \verb|$ | -- all states\\ +\fakeitem \verb|% | -- final states\\ +\fakeitem \verb|< | -- any state except the start state\\ +\fakeitem \verb|@ | -- any state except final states\\ +\fakeitem \verb|<>| -- any except start and final (middle) -Two variables are written that may be used to test the state of the machine -after a buffer block has been processed. The \verb|name_error| variable gives -the id of the state that the machine moves into when it cannot find a valid -transition to take. The machine immediately breaks out of the processing loop when -it finds itself in the error state. The error variable can be compared to the -current state to determine if the machine has failed to parse the input. If the -machine is complete, that is from every state there is a transition to a proper -state on every possible character of the alphabet, then no error state is required -and this variable will be set to -1. +\columnbreak -The \verb|name_first_final| variable stores the id of the first final state. All of the -machine's states are sorted by their final state status before having their ids -assigned. Checking if the machine has accepted its input can then be done by -checking if the current state is greater-than or equal to the first final -state. +\noindent The different kinds of embeddings are:\\ +\fakeitem \verb|~| -- to-state actions\\ +\fakeitem \verb|*| -- from-state actions\\ +\fakeitem \verb|/| -- EOF actions\\ +\fakeitem \verb|!| -- error actions\\ +\fakeitem \verb|^| -- local error actions\\ +\end{multicols} +\end{minipage} +%\label{state-act-embed} +%\caption{The two components of state embedding operators. The class of states +%to select comes first, followed by the type of embedding.} +% +%\begin{figure}[t] +%\centering +%\includegraphics{stembed} +%\caption{Summary of state manipulation operators} +%\label{state-act-embed-chart} +%\end{figure} -Data generation has several options: +%\noindent Putting these two components together we get a matrix of state +%embedding operators. The entire set is given in Figure \ref{state-act-embed-chart}. -\begin{itemize} -\item \verb|noerror| - Do not generate the integer variable that gives the -id of the error state. -\item \verb|nofinal| - Do not generate the integer variable that gives the -id of the first final state. -\item \verb|noprefix| - Do not prefix the variable names with the name of the -machine. -\end{itemize} -\subsection{Write Init} -\begin{verbatim} -write init; -\end{verbatim} -\verbspace +\subsection{To-State and From-State Actions} -The write init statement causes Ragel to emit initialization code. This should -be executed once before the machine is started. At a very minimum this sets the -current state to the start state. If other variables are needed by the -generated code, such as call -stack variables or longest-match management variables, they are also -initialized here. +\subsubsection{To-State Actions} -\subsection{Write Exec} -\begin{verbatim} -write exec [options]; -\end{verbatim} +\verb| >~ $~ %~ <~ @~ <>~ | \verbspace -The write exec statement causes Ragel to emit the state machine's execution code. -Ragel expects several variables to be available to this code. At a very minimum, the -generated code needs access to the current character position \verb|p|, the ending -position \verb|pe| and the current state \verb|cs|, though \verb|pe| -can be excluded by specifying the \verb|noend| write option. -The \verb|p| variable is the cursor that the execute code will -used to traverse the input. The \verb|pe| variable should be set up to point to one -position past the last valid character in the buffer. +To-state actions are executed whenever the state machine moves into the +specified state, either by a natural movement over a transition or by an +action-based transfer of control such as \verb|fgoto|. They are executed after the +in-transition's actions but before the current character is advanced and +tested against the end of the input block. To-state embeddings stay with the +state. They are irrespective of the state's current set of transitions and any +future transitions that may be added in or out of the state. -Other variables are needed when certain features are used. For example using -the \verb|fcall| or \verb|fret| statements requires \verb|stack| and -\verb|top| variables to be defined. If a longest-match construction is used, -variables for managing backtracking are required. +Note that the setting of the current state variable \verb|cs| outside of the +execute code is not considered by Ragel as moving into a state and consequently +the to-state actions of the new current state are not executed. This includes +the initialization of the current state when the machine begins. This is +because the entry point into the machine execution code is after the execution +of to-state actions. -The write exec statement has one option. The \verb|noend| option tells Ragel -to generate code that ignores the end position \verb|pe|. In this -case the user must explicitly break out of the processing loop using -\verb|fbreak|, otherwise the machine will continue to process characters until -it moves into the error state. This option is useful if one wishes to process a -null terminated string. Rather than traverse the string to discover then length -before processing the input, the user can break out when the null character is -seen. The example in Figure \ref{fbreak-example} shows the use of the -\verb|noend| write option and the \verb|fbreak| statement for processing a string. +\subsubsection{From-State Actions} -\begin{figure} -\small -\begin{verbatim} -#include -%% machine foo; -int main( int argc, char **argv ) -{ - %% write data noerror nofinal; - int cs, res = 0; - if ( argc > 1 ) { - char *p = argv[1]; - %%{ - main := - [a-z]+ - 0 @{ res = 1; fbreak; }; - write init; - write exec noend; - }%% - } - printf("execute = %i\n", res ); - return 0; -} -\end{verbatim} -\caption{Use of {\tt noend} write option and the {\tt fbreak} statement for -processing a string.} -\label{fbreak-example} -\end{figure} +\verb| >* $* %* <* @* <>* | +\verbspace +From-state actions are executed whenever the state machine takes a transition from a +state, either to itself or to some other state. These actions are executed +immediately after the current character is tested against the input block end +marker and before the transition to take is sought based on the current +character. From-state actions are therefore executed even if a transition +cannot be found and the machine moves into the error state. Like to-state +embeddings, from-state embeddings stay with the state. -\subsection{Write EOF Actions} -\begin{verbatim} -write eof; -\end{verbatim} -\verbspace +\subsection{EOF Actions} -The write EOF statement causes Ragel to emit code that executes EOF actions. -This write statement is only relevant if EOF actions have been embedded, -otherwise it does not generate anything. The EOF action code requires access to -the current state. +\verb| >/ $/ %/ / | +\verbspace -\section{Referencing Names} -\label{labels} +The EOF action embedding operators enable the user to embed EOF actions into +different classes of +states. EOF actions are stored in states and generated with the \verb|write eof| +statement. The generated EOF code switches on the current state and executes the EOF +actions associated with it. -This section describes how to reference names in epsilon transitions and -action-based control-flow statements such as \verb|fgoto|. There is a hierarchy -of names implied in a Ragel specification. At the top level are the machine -instantiations. Beneath the instantiations are labels and references to machine -definitions. Beneath those are more labels and references to definitions, and -so on. +\subsection{Handling Errors} -Any name reference may contain multiple components separated with the \verb|::| -compound symbol. The search for the first component of a name reference is -rooted at the join expression that the epsilon transition or action embedding -is contained in. If the name reference is not not contained in a join, -the search is rooted at the machine definition that that the epsilon transition or -action embedding is contained in. Each component after the first is searched -for beginning at the location in the name tree that the previous reference -component refers to. +\subsubsection{Global Error Actions} -In the case of action-based references, if the action is embedded more than -once, the local search is performed for each embedding and the result is the -union of all the searches. If no result is found for action-based references then -the search is repeated at the root of the name tree. Any action-based name -search may be forced into a strictly global search by prefixing the name -reference with \verb|::|. +\verb| >! $! %! ! | +\verbspace -The final component of the name reference must resolve to a unique entry point. -If a name is unique in the entire name tree it can be referenced as is. If it -is not unique it can be specified by qualifying it with names above it in the -name tree. However, it can always be renamed. +Error actions are stored in states until the final state machine has been fully +constructed. They are then transferred to the transitions that move into the +error state. This transfer entails the creation of a transition from the state +to the error state that is taken on all input characters which are not already +covered by the state's transitions. In other words it provides a default +action. Error actions can induce a recovery by altering \verb|p| and then jumping back +into the machine with \verb|fgoto|. -% FIXME: Should fit this in somewhere. -% Some kinds of name references are illegal. Cannot call into longest-match -% machine, can only call its start state. Cannot make a call to anywhere from -% any part of a longest-match machine except a rule's action. This would result -% in an eventual return to some point inside a longest-match other than the -% start state. This is banned for the same reason a call into the LM machine is -% banned. +\subsubsection{Local Error Actions} -\section{State Machine Minimization} +\verb| >^ $^ %^ <^ @^ <>^ | +\verbspace -State machine minimization is the process of finding the minimal equivalent FSM accepting -the language. Minimization reduces the number of states in machines -by merging equivalent states. It does not change the behaviour of the machine -in any way. It will cause some states to be merged into one because they are -functionally equivalent. State minimization is on by default. It can be turned -off with the \verb|-n| option. +Like global error actions, local error actions are also stored in states until +a transfer point. The transfer point is different however. Each local error action +embedding is associated with a name. When a machine definition has been fully +constructed, all local error actions embeddings associated the same name as the +machine are transferred to error transitions. Local error actions can be used +to specify an action to take when a particular section of a larger state +machine fails to make a match. A particular machine definition's ``thread'' may +die and the local error actions executed, however the machine as a whole may +continue to match input. -The algorithm implemented is similar to Hopcroft's state minimization -algorithm. Hopcroft's algorithm assumes a finite alphabet that can be listed in -memory, whereas Ragel supports arbitrary integer alphabets that cannot be -listed in memory. Though exact analysis is very difficult, Ragel minimization -runs close to $O(n \times log(n))$ and requires $O(n)$ temporary storage where -$n$ is the number of states. +There are two forms of local error action embeddings. In the first form the name defaults +to the current machine. In the second form the machine name can be specified. This +is useful when it is more convenient to specify the local error action in a +sub-definition that is used to construct the machine definition where the +transfer should happen. To embed local error actions and explicitly state the +machine on which the transfer is to happen use \verb|(name, action)| as the +action. -\chapter{User Actions} +\begin{comment} +\begin{itemize} +\setlength{\parskip}{0in} +\item \verb|expr >^ (name, action) | -- Start state. +\item \verb|expr $^ (name, action) | -- All states. +\item \verb|expr %^ (name, action) | -- Final states. +\item \verb|expr <^ (name, action) | -- Not start state. +\item \verb|expr <>^ (name, action)| -- Not start and not final states. +\end{itemize} +\end{comment} -Ragel permits the user to embed actions into the transitions of a regular -expression's corresponding state machine. These actions are executed when the -generated code moves over a transition. Like the regular expression operators, -the action embedding operators are fully compositional. They take a state -machine and an action as input, embed the action, and yield a new state machine -which can be used in the construction of other machines. Due to the -compositional nature of embeddings, the user has complete freedom in the -placement of actions. +\section{Action Ordering and Duplicates} -A machine's transitions are categorized into four classes, The action embedding -operators access the transitions defined by these classes. The {\em entering -transition} operator \verb|>| isolates the start state, then embeds an action -into all transitions leaving it. The {\em finishing transition} operator -\verb|@| embeds an action into all transitions going into a final state. The -{\em all transition} operator \verb|$| embeds an action into all transitions of -an expression. The {\em pending out transition} operator \verb|%| provides -access to yet-unmade leaving transitions. +When building a parser by combining smaller expressions which themselves have +embedded actions, it is often the case that transitions are made which need to +execute a number of actions on one input character. For example when we leave +an expression, we may execute the expression's pending out action and the +subsequent expression's starting action on the same input character. We must +therefore devise a method for ordering actions that is both intuitive and +predictable for the user and repeatable by the state machine compiler. The +determinization processes cannot simply order actions by the time at which they +are introduced into a transition -- otherwise the programmer will be at the +mercy of luck. -\section{Embedding Actions} +We associate with the embedding of each action a distinct timestamp which is +used to order actions that appear together on a single transition in the final +compiled state machine. To accomplish this we traverse the parse tree of +regular expressions and assign timestamps to action embeddings. This algorithm +is recursive in nature and quite simple. When it visits a parse tree node it +assigns timestamps to all {\em starting} action embeddings, recurses on the +parse tree, then assigns timestamps to the remaining {\em all}, {\em +finishing}, and {\em leaving} embeddings in the order in which they appear. + +Ragel does not permit actions (defined or unnamed) to appear multiple times in +an action list. When the final machine has been created, actions which appear +more than once in single transition or EOF action list have their duplicates +removed. The first appearance of the action is preserved. This is useful in a +number of scenarios. First, it allows us to union machines with common +prefixes without worrying about the action embeddings in the prefix being +duplicated. Second, it prevents pending out actions from being transferred multiple times +when a concatenation follows a kleene star and the two machines begin with a common +character. +\verbspace \begin{verbatim} -action ActionName { - /* Code an action here. */ - count += 1; -} +word = [a-z]+ %act; +main := word ( '\n' word )* '\n\n'; \end{verbatim} -\verbspace -The action statement defines a block of code that can be embedded into an FSM. -Action names can be referenced by the action embedding operators in -expressions. Though actions need not be named in this way (literal blocks -of code can be embedded directly when building machines), defining reusable -blocks of code whenever possible is good practice because it potentially increases the -degree to which the machine can be minimized. Within an action some Ragel expressions -and statements are parsed and translated. These allow the user to interact with the machine -from action code. See Section \ref{vals} for a complete list of statements and -values available in code blocks. +\section{Values and Statements Available in Code Blocks} +\label{vals} -\subsection{Entering Action} +\noindent The following values are available in code blocks: -\verb|expr > action| -\verbspace +\begin{itemize} +\item \verb|fpc| -- A pointer to the current character. This is equivalent to +accessing the \verb|p| variable. -The entering operator embeds an action into the starting transitions. The -action is executed on all transitions that enter into the machine from the -start state. If the start state is a final state then it is possible for the -machine to never be entered and the starting transitions bypassed. In the -following example, the action is executed on the first transition of the -machine. If the repetition machine is bypassed the action is not executed. +\item \verb|fc| -- The current character. This is equivalent to the expression \verb|(*p)|. -\verbspace +\item \verb|fcurs| -- An integer value representing the current state. This +value should only be read from. To move to a different place in the machine +from action code use the \verb|fgoto|, \verb|fnext| or \verb|fcall| statements. +Outside of the machine execution code the \verb|cs| variable may be modified. -% GENERATE: exstact -% OPT: -p -% %%{ -% machine exstact; -\begin{inline_code} -\begin{verbatim} -# Execute A at the beginning of a string of alpha. -action A {} -main := ( lower* >A ) . ' '; -\end{verbatim} -\end{inline_code} -% }%% -% END GENERATE +\item \verb|ftargs| -- An integer value representing the target state. This +value should only be read from. Again, \verb|fgoto|, \verb|fnext| and +\verb|fcall| can be used to move to a specific entry point. -\graphspace -\begin{center} -\includegraphics[scale=0.45]{exstact} -\end{center} -\graphspace +\item \verb|fentry(